Dominating plane triangulations

DOI10.1016/J.DAM.2016.04.011MaRDI QIDQ335349zbMATH OpenOpenAlexFDO

Authors Michael D. Plummer, Dong Ye, Xiaoya Zha

Publication date 2 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.4530

zbMATH Keywords

dominationHamilton cycleouterplanar graphplane triangulation

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)

Abstract: In 1996, Tarjan and Matheson proved that if $G$ is a plane triangulated disc with $n$ vertices, $gamma(G)len/3$, where $gamma(G)$ denotes the domination number of $G$. Furthermore, they conjectured that the constant $1/3$ could be improved to $1/4$ for sufficiently large $n$. Their conjecture remains unsettled. In the present paper, it is proved that if $G$ is a hamiltonian plane triangulation with $|V(G)|=n$ vertices and minimum degree at least 4, then $gamma(G)lemaxlceil2n/7ceil,lfloor5n/16floor$. It follows immediately that if $G$ is a 4-connected plane triangulation with $n$ vertices, then $gamma(G)lemaxlceil2n/7ceil,lfloor5n/16floor$. It then follows that if $nge26$, then $gamma(G)lelfloor5n/16floor$.

Recommendations

• Dominating sets in plane triangulations
• The domination number of plane triangulations
• Dominating maximal outerplane graphs and Hamiltonian plane triangulations
• Total domination in plane triangulations
• Dominating sets in triangulations on surfaces

Cites work

• A Theorem on Planar Graphs
• A note on the domination number of triangulations
• DOMINATION IN GRAPHS OF MINIMUM DEGREE FOUR
• Dominating sets in planar graphs
• Dominating sets in plane triangulations
• Dominating sets in triangulations on surfaces
• On certain spanning subgraphs of embeddings with applications to domination
• On dominating sets of maximal outerplanar graphs

Cited in

(11)

• Total domination in plane triangulations
• Domination of triangulated discs and maximal outerplanar graphs
• Domination number of annulus triangulations
• Independent dominating sets in planar triangulations
• Dominating sets in plane triangulations
• The domination number of plane triangulations
• Types of triangle in Hamiltonian triangulations and an application to domination and \(k\)-walks
• On certain spanning subgraphs of embeddings with applications to domination
• Dominating maximal outerplane graphs and Hamiltonian plane triangulations
• Dominating sets in triangulations on surfaces
• A note on the domination number of triangulations

This page was built for publication: Dominating plane triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q335349)