Partial domination of maximal outerplanar graphs

Abstract

Several domination results have been obtained for maximal outerplanar graphs (mops). The classical domination problem is to minimize the size of a set S of vertices of an n-vertex graph G such that G − N[S], the graph obtained by deleting the closed neighborhood of S, is null. A classical result of Chvátal is that the minimum size is at most n/3 if G is a mop. Here we consider a modification by allowing G − N[S] to have isolated vertices and isolated edges only. Let ι1(G) denote the size of a smallest set S for which this is achieved. We show that if G is a mop on n ≥ 5 vertices, and n2 is the number of vertices of degree 2, then ι1(G) ≤ n/5 and ι1(G) ≤ { n+n2 6 if n2 ≤ n3, n−n2 3 otherwise. We also show that these bounds are best possible.