Dominating sets of maximal outerplanar graphs
A dominating set D?V D ? V of a graph G G is a set such that each vertex v?V v ? V is either in the set or adjacent to a vertex in the set. We show that if G G is an n n -vertex maximal outerplanar graph with n?3 n ? 3 having k k vertices of degree 2 2 , then G G has a dominating set of size at most ? n + k 4 ? , by a simple coloring method.
dominating set outerplanar graph coloring domination number plane graph triangulation induced path