Dominating Sets in Plane Triangulations

Abstract

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.

arXiv comment14 pages, 6 figures; Revised lemmas 6-8, clarified arguments and fixed typos, result unchanged