Dominating sets in triangulations on surfaces - Liu, Hong (Ars mathematica contemporanea, 2011)
A dominating set ?$D \subset V(G)$? of a graph ?$G$? is a set such that each vertex ?$v \in V(G)$? is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any ?$n$?-vertex plane triangulation has a dominating set of size at most ?$n/3$?, and conjectured a bound of ?$n/4$? for ?$n$? sufficiently large. King and Pelsmajer recently proved this for graphs with maximum degree at most 6. Plummer and Zha (2009) and Honjo, Kawarabayashi, and Nakamoto (2009) extended the ?$n/3$? bound to triangulations on surfaces. We prove two related results: (i) There is a constant ?$c_1$? such that any ?$n$?-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most ?$n/6 + c_1$?. (ii) For any surface ?$S$?, ?$t \ge 0$?, and ?$ε > 0$?, there exists ?$c_2$? such that for any ?$n$?-vertex triangulation on ?$S$? with at most ?$t$? vertices of degree other than 6, there is a dominating set of size at most ?$n(1/6 + ε) + c_2$?. As part of the proof, we also show that any ?$n$?-vertex triangulation of a non-orientable surface has a non-contractible cycle of length at most ?$2\sqrt{n}$?. Albertson and Hutchinson (1986) proved that for ?$n$?-vertex triangulation of an orientable surface other than a sphere has a non-contractible cycle of length ?$2\sqrt{2n}$?, but no similar result was known for non-orientable surfaces.
Keywords: dominacijska množica; dominating set; grafi na ploskvah; graph theory; graphs on surfaces; neorientabilna ploskev; nestisljiv cikel; non-contractible cycle; non-orientable surface; teorija grafov; triangulacija; triangulation