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 ${\iota }_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\ge 5$ vertices, then ${\iota }_1(G)\le n/5$. We also show that if $n_2$ is the number of vertices of degree $2$, then ${\iota }_1(G)\le \frac{n+n_2}{6}$ if $n_2\le \frac{n}{3}$, and ${\iota }_1(G)\le \frac{n-n_2}{3}$ otherwise. We show that these bounds are best possible.

14 pages