Dominating maximal outerplane graphs and Hamiltonian plane triangulations

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) <= n/4. Their conjecture remains unsettled. In the present paper, we show that: (1) a maximal outerplane graph with n vertices has gamma(G) <= [n+k/4] 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 >= 23 vertices has gamma (G) <= 5n/16. We also point out and provide counterexamples for several recent published results of Li et al. (2016) on this topic which are incorrect. (C) 2019 Elsevier B.V. All rights reserved.