Distance domination, guarding and covering of maximal outerplanar graphs
In this paper we introduce the notion of distance k k -guarding applied to triangulation graphs, and associate it with distance k k -domination and distance k k -covering. We obtain results for maximal outerplanar graphs when k=2 k = 2 . A set S S of vertices in a triangulation graph T T is a distance 2-guarding set (or 2d 2 d -guarding set for short) if every face of T T has a vertex adjacent to a vertex of S S . We show that ? n 5 ? (respectively, ? n 4 ? ) vertices are sufficient to 2d 2 d -guard and 2d 2 d -dominate (respectively, 2d 2 d -cover) any n n -vertex maximal outerplanar graph. We also show that these bounds are tight.
domination guarding covering triangulation graphs