Article ID Journal Published Year Pages File Type
6871870 Discrete Applied Mathematics 2016 8 Pages PDF
Abstract
In 1996, Tarjan and Matheson proved that if G is a plane triangulated disc with n vertices, γ(G)≤n/3, where γ(G) denotes the domination number of G, i.e. the cardinality of the smallest set of vertices S such that every vertex of G is either in S or adjacent to a vertex in S. Furthermore, they conjectured that the constant 1/3 could be improved to 1/4 for a sufficiently large n. Their conjecture remains unsettled. In the present paper, it is proved that if G is a Hamiltonian plane triangulation with n vertices and minimum degree at least 4, then γ(G)≤max{⌈2n/7⌉,⌊5n/16⌋}. It follows immediately that if G is a 4-connected plane triangulation with n vertices, then γ(G)≤max{⌈2n/7⌉,⌊5n/16⌋}.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,