### Dominating sets in triangulations on surfaces

#### Abstract

A

We prove two related results: (i) There is a constant

As part of the proof, we also show that any

*dominating set**D*⊆*V*(*G*) of a graph*G*is a set such that each vertex*v*∈*V*(*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*_{1}such that any*n*-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most*n*/6 +*c*_{1}. (ii) For any surface*S*,*t*≥ 0, and*ε*> 0, there exists*c*_{2}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 +*ε*) +*c*_{2}.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 √(2*n*), but no similar result was known for non-orientable surfaces.#### Keywords

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

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