{
  "id": "1006.1879",
  "version": "v4",
  "published": "2010-06-09T19:23:25.000Z",
  "updated": "2011-03-29T22:20:29.000Z",
  "title": "Dominating Sets in Triangulations on Surfaces",
  "authors": [
    "Hong Liu",
    "Michael J. Pelsmajer"
  ],
  "comment": "26 pages, 12 figures; small fix",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2011-03-29T22:20:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C69"
    ],
    "keywords": [
      "dominating set",
      "n-vertex plane triangulation",
      "n-vertex triangulation",
      "maximum degree",
      "non-orientable surface"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1006.1879L"
    }
  }
}