Mathematics – Combinatorics
Scientific paper
2010-06-09
Mathematics
Combinatorics
26 pages, 12 figures; small fix
Scientific paper
A dominating set D of a graph G is a set such that each vertex v of 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 such that any n-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most n/6 + c. (ii) For any surface S, nonnegative t, and epsilon > 0, there exists C 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 + epsilon) + C. 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 2sqrt(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 sqrt(2n), but no similar result was known for non-orientable surfaces.
Liu Hong
Pelsmajer Michael J.
No associations
LandOfFree
Dominating Sets in Triangulations on Surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dominating Sets in Triangulations on Surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dominating Sets in Triangulations on Surfaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-40373