Dominating sets in triangulations on surfaces

Hong Liu, Michael J. Pelsmajer

Abstract


A dominating set DV(G) of a graph G is a set such that each vertex vV(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 c1 such that any n-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most n/6 + c1. (ii) For any surface S, t ≥ 0, and ε > 0, there exists c2 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 + ε) + c2.
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 2√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 √(2n), but no similar result was known for non-orientable surfaces.

Keywords


dominating set, triangulation, graphs on surfaces, non-contractible cycle, non-orientable surface

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.200.fbe

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications