2014年2月
A note on distance dominating in maximal outerplanar graphs
研究報告アルゴリズム(AL)
- ,
- ,
- 巻
- 2014
- 号
- 14
- 開始ページ
- 1
- 終了ページ
- 3
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- 一般社団法人情報処理学会
In a graph G, a node v is said to (distance) k-dominate a node w if w is reachable from v by a path with at most k edges. The size of a minimum set that k-dominates all nodes is called the (distance) k-domination number of G, denoted by γk(G). It is known that, for a maximal outerplanar graph G with n nodes, γ1(G)≦|n=3| and it is tight (Matheson and Tarjan, 1996, with a linear-time construction algorithm), and γ2(G)≦|n/5| and it is tight too (Canales et al., 2013, with no algorithm). This study gives a simpler proof and a construction algorithm for the latter result.In a graph G, a node v is said to (distance) k-dominate a node w if w is reachable from v by a path with at most k edges. The size of a minimum set that k-dominates all nodes is called the (distance) k-domination number of G, denoted by γk(G). It is known that, for a maximal outerplanar graph G with n nodes, γ1(G)≦|n=3| and it is tight (Matheson and Tarjan, 1996, with a linear-time construction algorithm), and γ2(G)≦|n/5| and it is tight too (Canales et al., 2013, with no algorithm). This study gives a simpler proof and a construction algorithm for the latter result.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110009675763
- CiNii Books
- http://ci.nii.ac.jp/ncid/AN1009593X
- ID情報
-
- ISSN : 0919-6072
- CiNii Articles ID : 110009675763
- CiNii Books ID : AN1009593X
- identifiers.cinii_nr_id : 9000018481536