Dominating sets in triangulations on surfaces |
| |
Authors: | Tatsuya Honjo Ken‐ichi Kawarabayashi Atsuhiro Nakamoto |
| |
Affiliation: | 1. Department of Mathematics, Faculty of Education and Human Sciences, Yokohama National University Tokiwadai, Yokohama 240‐8501, Japan;2. Principles of Informatics Research Division, National Institute of Informatics Hitotsubashi, Tokyo 101‐8430, Japan |
| |
Abstract: | 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 |
| |
Keywords: | dominating set triangulation projective plane torus Klein bottle representativity |
|
|