Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871870 | Discrete Applied Mathematics | 2016 | 8 Pages |
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
Michael D. Plummer, Dong Ye, Xiaoya Zha,