{
  "id": "1404.1382",
  "version": "v1",
  "published": "2014-04-04T20:04:12.000Z",
  "updated": "2014-04-04T20:04:12.000Z",
  "title": "Domination game on forests",
  "authors": [
    "Csilla Bujtás"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In the domination game studied here, Dominator and Staller alternately choose a vertex of a graph $G$ and take it into a set $D$. The number of vertices dominated by the set $D$ must increase in each single turn and the game ends when $D$ becomes a dominating set of $G$. Dominator aims to minimize whilst Staller aims to maximize the number of turns (or equivalently, the size of the dominating set $D$ obtained at the end). Assuming that Dominator starts and both players play optimally, the number of turns is called the game domination number $\\gamma_g(G)$ of $G$. Kinnersley, West and Zamani verified that $\\gamma_g(G) \\le 7n/11$ holds for every isolate-free $n$-vertex forest $G$ and they conjectured that the sharp upper bound is only $3n/5$. Here, we prove the 3/5-conjecture for forests in which no two leaves are at distance 4 apart. Further, we establish an upper bound $\\gamma_g(G) \\le 5n/8$, which is valid for every isolate-free forest $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-04T20:04:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57",
      "05C69",
      "91A43"
    ],
    "keywords": [
      "domination game",
      "sharp upper bound",
      "dominating set",
      "minimize whilst staller aims",
      "game domination number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.1382B"
    }
  }
}