{
  "id": "1210.0524",
  "version": "v2",
  "published": "2012-10-01T19:58:18.000Z",
  "updated": "2013-03-13T16:54:45.000Z",
  "title": "Domination game played on trees and spanning subgraphs",
  "authors": [
    "Bostjan Bresar",
    "Sandi Klavzar",
    "Douglas F. Rall"
  ],
  "comment": "16 pages, 9 figures",
  "journal": "Discrete Mathematics 313(2013) 915-923",
  "doi": "10.1016/j.disc.2013.01.014",
  "categories": [
    "math.CO"
  ],
  "abstract": "The domination game is played on a graph G. Vertices are chosen, one at a time, by two players Dominator and Staller. Each chosen vertex must enlarge the set of vertices of G dominated to that point in the game. Both players use an optimal strategy---Dominator plays so as to end the game as quickly as possible while Staller plays in such a way that the game lasts as many steps as possible. The game domination number of G is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number of G when Staller starts the game. In this paper these two games are studied when played on trees and spanning subgraphs. A lower bound for the game domination number of a tree in terms of the order and maximum degree is proved and shown to be asymptotically tight. It is shown that for every k, there is a tree T with game domination number k and Staller-start game domination number k+1, and it is conjectured that there is no tree with game domination number k and Staller-start game domination number k-1. A relation between the game domination number of a graph and its spanning subgraphs is considered. It is proved that for any positive integer n, there exists a graph G and its spanning tree T such that the game domination number of G is at least n more than the game domination number of T. Moreover, there exist 3-connected graphs G having a spanning subgraph such that the game domination number of the spanning subgraph is arbitrarily smaller than that of G.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-03-13T16:54:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57",
      "91A43",
      "05C69"
    ],
    "keywords": [
      "spanning subgraph",
      "staller-start game domination number",
      "domination game",
      "optimal strategy-dominator plays",
      "staller plays"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.0524B"
    }
  }
}