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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- DOMINATION IN GRAPHS OF MINIMUM DEGREE FOUR
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Dominating sets in planar graphs
- Dominating sets in triangulations on surfaces
- Domination in graphs of minimum degree five
- 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
- Paths, Stars and the Number Three
Cited in
(22)- On dominating sets of maximal outerplanar and planar graphs
- Total domination in plane triangulations
- Domination of triangulated discs and maximal outerplanar graphs
- Domination number of annulus triangulations
- Stack domination density
- On the domination of triangulated discs
- Bounds for the connected domination number of maximal outerplanar graphs
- Dominating plane triangulations
- Independent dominating sets in planar triangulations
- Distance domination, guarding and covering of maximal outerplanar graphs
- Domination number of graphs with minimum degree five
- The domination number of plane triangulations
- Dominating sets of maximal outerplanar graphs
- On certain spanning subgraphs of embeddings with applications to domination
- Domination of maximal \(K_4\)-minor free graphs and maximal \(K_{2, 3}\)-minor free graphs, and disproofs of two conjectures on planar graphs
- Dominating sets in triangulations on surfaces
- On the dominating set polytope
- Dominating maximal outerplane graphs and Hamiltonian plane triangulations
- Dominating sets in triangulations on surfaces
- A note on vertices contained in the minimum dominating set of a graph with minimum degree three
- Geometric dominating sets -- a minimum version of the no-three-in-line problem
- A note on the domination number of triangulations
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)
