A note on distance dominating in maximal outerplanar graphs

概要

論文の詳細を見る
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.
2014-02-24