Dominating sets in plane triangulations

DOI10.1016/J.DISC.2010.03.022MaRDI QIDQ708360zbMATH OpenOpenAlexFDO

Authors Erika L. C. King, Michael J. Pelsmajer

Publication date 11 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dominating setdomination numberplane triangulationtriangulated disc

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: In 1996, Matheson and Tarjan conjectured that any n-vertex triangulation with n sufficiently large has a dominating set of size at most n/4. We prove this for graphs of maximum degree 6.

Review text

A dominating set \(D \subseteq V\) of a graph \(G(V,E)\) is a set such that each vertex \(v \in V\) is either in the set or is adjacent to a vertex in the set. The domination number of \(G\) denoted by \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). In 1996, \textit{L.R. Matheson} and \textit{R.E. Tarjan} [``Dominating sets in planar graphs, Eur. J. Comb. 17, No.\,6, 565--568 (1996; Zbl 0862.05032)] considered this asymptotically for plane triangulations. They proved that any any triangulated disc \(G\) with \(n\) vertices has \(\gamma(G)\leq n/3\). They conjectured that this bound can be improved if the disc is bounded by a triangle. In this paper, the authors proves this conjecture for graphs of maximum degree 6.

Recommendations

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

Cites work

• Dominating sets in planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Dominating sets in triangulations on surfaces
• Domination in graphs of minimum degree five
• DOMINATION IN GRAPHS OF MINIMUM DEGREE FOUR
• Domination in planar graphs with small diameter II.
• Domination in planar graphs with small diameter*
• Domination numbers of planar graphs
• Encoding Fullerenes and Geodesic Domes
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Paths, Stars and the Number Three

Cited in

(25)

• On certain spanning subgraphs of embeddings with applications to domination
• Dominating sets in planar graphs
• Geometric dominating sets -- a minimum version of the no-three-in-line problem
• Bounds for the connected domination number of maximal outerplanar graphs
• The domination number of plane triangulations
• Dominating maximal outerplane graphs and Hamiltonian plane triangulations
• Total domination in plane triangulations
• On the dominating set polytope
• Dominating sets of maximal outerplanar graphs
• Stack domination density
• Domination number of graphs with minimum degree five
• A note on vertices contained in the minimum dominating set of a graph with minimum degree three
• Dominating sets in triangulations on surfaces
• Dominating plane triangulations
• Distance domination, guarding and covering of maximal outerplanar graphs
• Domination of maximal \(K_4\)-minor free graphs and maximal \(K_{2, 3}\)-minor free graphs, and disproofs of two conjectures on planar graphs
• Domination number of annulus triangulations
• Dominating sets in triangulations on surfaces
• A note on the domination number of triangulations
• On the domination of triangulated discs
• Independent dominating sets in planar triangulations
• Domination of triangulated discs and maximal outerplanar graphs
• Connected domination in plane triangulations
• Independent dominating sets in planar triangulations (extended abstract)
• On dominating sets of maximal outerplanar and planar graphs

This page was built for publication: Dominating sets in plane triangulations

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