2019/03/06 by Michael D. Plummer, Plummer, Michael D., Dong Ye +3
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1903.02462
openalex publication_date 2019/03/06 · openalex created_date 2019/04/01 · openalex updated_date 2026/07/28
Let G be a graph and γ(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 γ(G)≤ n/4. Their conjecture remains unsettled. In the present paper, we show that: (1) a maximal outerplane graph with n vertices has γ(G)≤ \lceil \fracn+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 ≥ 23 vertices has γ(G)≤ 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.