Dominating sets in triangulations on surfaces

Let G be a graph and let S ⊂ V ( G ). We say that S is dominating in G if each vertex of G is in S or adjacent to a vertex in S . We show that every triangulation on the torus and the Klein bottle with n vertices has a dominating set of cardinality at most \documentclass{article}\usepackage{amssymb}\footskip=0pc\pagestyle{empty}\begin{document} $\frac{n}{3}$ \end{document} . Moreover, we show that the same conclusion holds for a triangulation on any non‐spherical surface with sufficiently large representativity. These results generalize that for plane triangulations proved by Matheson and Tarjan (European J Combin 17 (1996), 565–568), and solve a conjecture by Plummer (Private Communication). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 17–30, 2010