{
  "id": "1701.06012",
  "version": "v1",
  "published": "2017-01-21T11:29:23.000Z",
  "updated": "2017-01-21T11:29:23.000Z",
  "title": "An evasion game on a graph",
  "authors": [
    "John Haslegrave"
  ],
  "comment": "This is an old paper from 2011 (accepted 2013) that I neglected to put on arXiv at the time. These results have since been independently obtained by Britnell & Wildon and by Komorov & Winkler",
  "journal": "Discrete Mathematics, Volume 314, 6 January 2014, Pages 1-5, ISSN 0012-365X",
  "doi": "10.1016/j.disc.2013.09.004",
  "categories": [
    "math.CO"
  ],
  "abstract": "This paper introduced a pursuit and evasion game to be played on a connected graph. One player moves invisibly around the graph, and the other player must guess his position. At each time step the second player guesses a vertex, winning if it is the current location of the first player; if not the first player must move along an edge. It is shown that the graphs on which the second player can guarantee to win are precisely the trees that do not contain a particular forbidden subgraph, and best possible capture times on such graphs are obtained.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-21T11:29:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57"
    ],
    "keywords": [
      "evasion game",
      "first player",
      "second player guesses",
      "forbidden subgraph",
      "time step"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Elsevier"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}