Partial domination of maximal outerplanar graphs
read the original 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\'{a}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 \geq 5$ vertices, then $\iota_{1}(G) \leq n/5$. We also show that if $n_2$ is the number of vertices of degree $2$, then $\iota_{1}(G) \leq \frac{n+n_2}{6}$ if $n_2 \leq \frac{n}{3}$, and $\iota_1(G) \leq \frac{n-n_2}{3}$ otherwise. We show that these bounds are best possible.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.