Dominating sets in plane triangulations
From MaRDI portal
Publication:708360
DOI10.1016/J.DISC.2010.03.022zbMATH Open1203.05120arXiv0806.2421OpenAlexW2068102400MaRDI QIDQ708360FDOQ708360
Authors: Erika L. C. King, Michael J. Pelsmajer 
Publication date: 11 October 2010
Published in: Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0806.2421
Recommendations
Cites Work
- Title not available (Why is that?)
- Dominating sets in triangulations on surfaces
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Domination in graphs of minimum degree five
- DOMINATION IN GRAPHS OF MINIMUM DEGREE FOUR
- Paths, Stars and the Number Three
- Encoding Fullerenes and Geodesic Domes
- Dominating sets in planar graphs
- Domination in planar graphs with small diameter II.
- Domination in planar graphs with small diameter*
- Domination numbers of planar graphs
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
- Independent dominating sets in planar triangulations
- Dominating plane 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
- A note on the domination number of triangulations
- Geometric dominating sets -- a minimum version of the no-three-in-line problem
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)
