{
  "id": "0805.2709",
  "version": "v1",
  "published": "2008-05-18T01:08:38.000Z",
  "updated": "2008-05-18T01:08:38.000Z",
  "title": "Cops and robbers in random graphs",
  "authors": [
    "Bela Bollobas",
    "Gabor Kun",
    "Imre Leader"
  ],
  "comment": "15 pages. J. Comb. Theory B, submitted",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the pursuit and evasion game on finite, connected, undirected graphs known as cops and robbers. Meyniel conjectured that for every graph on n vertices a rootish number of cops can win the game. We prove that this holds up to a log(n) factor for random graphs G(n,p) if p is not very small, and this is close to be tight unless the graph is very dense. We analyze the area-defending strategy (used by Aigner in case of planar graphs) and show examples where it can not be too efficient.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-05-18T01:08:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "random graphs",
      "evasion game",
      "planar graphs",
      "undirected graphs",
      "rootish number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0805.2709B"
    }
  }
}