Dominating Sets in Plane Triangulations

2008/06/15 by King, Erika L. C., Pelsmajer, Michael J. · 1 citation
#05C10 #05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0806.2421

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.

Cited by

• Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets

Related

• Dominating Sets in Triangulations on Surfaces
• The domination number of plane triangulations
• Triangulations Admit Dominating Sets of Size 2n/7
• Dominating Plane Triangulations
• Independent dominating sets in planar triangulations