MISC

2014年2月

A note on distance dominating in maximal outerplanar graphs

研究報告アルゴリズム(AL)
  • Liang Zhao
  • ,
  • Jia Li
  • ,
  • Dorothea Wagner

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

エクスポート
BibTeX RIS