Premium
Dominating sets in triangulations on surfaces
Author(s) -
Honjo Tatsuya,
Kawarabayashi Kenichi,
Nakamoto Atsuhiro
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20401
Subject(s) - combinatorics , klein bottle , mathematics , vertex (graph theory) , conjecture , torus , triangulation , graph , dominating set , cardinality (data modeling) , geometry , computer science , data mining
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