arXiv Analytics

Sign in

arXiv:0806.2421 [math.CO]AbstractReferencesReviewsResources

Dominating Sets in Plane Triangulations

Erika L. C. King, Michael J. Pelsmajer

Published 2008-06-15, updated 2010-06-07Version 2

In 1996, Matheson and Tarjan conjectured that any n-vertex triangulation with n sufficiently large has a dominating set of size at most n/4. We prove this for graphs of maximum degree 6.

Comments: 14 pages, 6 figures; Revised lemmas 6-8, clarified arguments and fixed typos, result unchanged
Categories: math.CO
Subjects: 05C10, 05C69
Related articles: Most relevant | Search more
arXiv:1006.1879 [math.CO] (Published 2010-06-09, updated 2011-03-29)
Dominating Sets in Triangulations on Surfaces
arXiv:2103.03053 [math.CO] (Published 2021-03-04)
Graphs with disjoint 2-dominating sets
arXiv:0905.3268 [math.CO] (Published 2009-05-20)
Dominating sets and Domination polynomials of Cycles

Links

Toolbox