{
  "id": "1301.0282",
  "version": "v1",
  "published": "2013-01-02T17:54:46.000Z",
  "updated": "2013-01-02T17:54:46.000Z",
  "title": "Component Games on Regular Graphs",
  "authors": [
    "Rani Hod",
    "Alon Naor"
  ],
  "comment": "10 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We study the (1:b) Maker-Breaker component game, played on the edge set of a d-regular graph. Maker's aim in this game is to build a large connected component, while Breaker's aim is to not let him do so. For all values of Breaker's bias b, we determine whether Breaker wins (on any d-regular graph) or Maker wins (on almost every d-regular graph) and provide explicit winning strategies for both players. To this end, we prove an extension of a theorem by Gallai-Hasse-Roy-Vitaver about graph orientations without long directed simple paths.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-01-02T17:54:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "91A24",
      "68R10"
    ],
    "keywords": [
      "regular graphs",
      "d-regular graph",
      "maker-breaker component game",
      "long directed simple paths",
      "large connected component"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}