2010/06/09 by Hong Liu, Liu, Hong, Michael J. Pelsmajer +1
Computer Science · Mathematics · #05C10 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Mathematics #math.CO #msc:05C10 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1006.1879
26 pages, 12 figures; small fix
openalex publication_date 2010/06/09 · arxiv created 2011/03/29 · arxiv updated 2011/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A dominating set D of a graph G is a set such that each vertex v of G is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any n-vertex plane triangulation has a dominating set of size at most n/3, and conjectured a bound of n/4 for n sufficiently large. King and Pelsmajer recently proved this for graphs with maximum degree at most 6. Plummer and Zha (2009) and Honjo, Kawarabayashi, and Nakamoto (2009) extended the n/3 bound to triangulations on surfaces. We prove two related results: (i) There is a constant c such that any n-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most n/6 + c. (ii) For any surface S, nonnegative t, and epsilon > 0, there exists C such that for any n-vertex triangulation on S with at most t vertices of degree other than 6, there is a dominating set of size at most n(1/6 + epsilon) + C. As part of the proof, we also show that any n-vertex triangulation of a non-orientable surface has a non-contractible cycle of length at most 2sqrt(n). Albertson and Hutchinson (1986) proved that for n-vertex triangulation of an orientable surface other than a sphere has a non-contractible cycle of length sqrt(2n), but no similar result was known for non-orientable surfaces.