  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.
