Dominating maximal outerplane graphs and Hamiltonian plane triangulations

Abstract

Let $G$ be a graph and $\gamma (G)$ denote the domination number of $G$, i.e. the cardinality of a smallest set of vertices $S$ such that every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. Matheson and Tarjan conjectured that a plane triangulation with a sufficiently large number $n$ of vertices has $\gamma (G)\le n/4$. Their conjecture remains unsettled. In the present paper, we show that: (1) a maximal outerplane graph with $n$ vertices has $\gamma (G)\le \lceil \frac{n+k}{4}\rceil$ where $k$ is the number of pairs of consecutive degree 2 vertices separated by distance at least 3 on the boundary of $G$; and (2) a Hamiltonian plane triangulation $G$ with $n\ge 23$ vertices has $\gamma (G)\le 5n/16$. We also point out and provide counterexamples for several recent published results of Li et al in [Discrete Appl. Math.198 (2016) 164-169] on this topic which are incorrect.

9 pages, 2 figures