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 $\frac{n}{3}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 $\frac{n}{3}$. 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