| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-03-04 10:30 極大外平面グラフの二重支配数の上界 ○荒木 徹（群馬大）  COMP2025-22 |
|
| 抄録 | （和） | グラフ$G$の頂点の部分集合$S$は，$G$のすべての頂点が2個以上の$S$の頂点 から支配されているならば，$S$を二重支配集合という。$G$の最小の二重支 配集合の頂点数を$G$の二重支配数といい，$gamma_{times 2}(G)$と表す。 本論文では，任意の極大外平面グラフ$G$に対して，$gamma_{times 2}(G) leq (n+k)/2$であることを示す。ここで$k$は距離が3以上離れている外周上で連 続する次数2の頂点のペアの数である。この結果はAbd Azizら (2022) によっ て発表されているが，その証明には誤りがある。本論文では，この命題に対 する完全な証明を与えて，命題が正しいことを示した。 |
| （英） | In a graph $G$, a vertex dominates itself and its neighbors. A subset $S$ of vertices of $G$ is a double dominating set of $G$ if every vertex is dominated by at least two vertices in $S$. The double domination number $gamma_{times 2}(G)$ of $G$ is the minimum cardinality of a double dominating set of $G$. In this paper, we prove that, for a maximal outerplanar graph $G$, the double domination number $gamma_{times 2}(G)$ is at most $(n+k)/2$, where $k$ is the number of pairs of consecutive on the outer cycle but at distance at least 3. Although this bound was previously proposed by Abd Aziz, Rad and Kamarulhaili (A note on the double domination number in maximal outerplanar and planar graphs, RAIRO Operations Research, 56 (2022) 3367--3371), their proof was found to be incomplete. In this paper we establish the validity of this result by providing a complete proof. |
|
| キーワード | （和） | 二重支配集合 / 支配集合 / 極大外平面グラフ / 上界 / / / / |
| （英） | double dominating set / dominating set / maximal outerplanar graph / upper bound / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 390, COMP2025-22, pp. 5-12, 2026年3月. | |
| 資料番号 | COMP2025-22 | |
| 発行日 | 2026-02-25 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2025-22 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2026-03-04 - 2026-03-04 |
| 開催地（和） | 中央大学後楽園キャンパス 6号館4階6402 |
| 開催地（英） | Chuo University Korakuen Campus Building 6 4F Room 6402 |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, General |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2026-03-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 極大外平面グラフの二重支配数の上界 |
| サブタイトル（和） | |
| タイトル（英） | An upper bound for the double domination number of maximal outerplanar graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 二重支配集合 / double dominating set |
| キーワード(2)（和/英） | 支配集合 / dominating set |
| キーワード(3)（和/英） | 極大外平面グラフ / maximal outerplanar graph |
| キーワード(4)（和/英） | 上界 / upper bound |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 荒木 徹 / Toru Araki / アラキ トオル |
| 第1著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-03-04 10:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2025-22 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.390 |
| ページ範囲 | pp.5-12 |
| ページ数 | 8 |
| 発行日 | 2026-02-25 (COMP) |
[研究会発表申込システムのトップページに戻る]