{
  "id": "1312.7555",
  "version": "v3",
  "published": "2013-12-29T16:37:34.000Z",
  "updated": "2014-09-28T02:12:49.000Z",
  "title": "Cops and Robbers on diameter two graphs",
  "authors": [
    "Zsolt A. Wagner"
  ],
  "comment": "5 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In this short paper we study the game of Cops and Robbers, played on the vertices of some fixed graph $G$ of order $n$. The minimum number of cops required to capture a robber is called the cop number of $G$. We show that the cop number of graphs of diameter 2 is at most $\\sqrt{2n}$, improving a recent result of Lu and Peng by a constant factor. We conjecture that this bound is still not optimal, and obtain some partial results towards the optimal bound.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-04-07T11:33:19.000Z",
      "abstract": "In this short paper we study the game of Cops and Robbers, played on the vertices of some fixed graph $G$ of order $n$. The minimum number of cops required to capture a robber is called the cop number of $G$. We show that the cop number of graphs of diameter 2 is at most $\\sqrt{2n}$, improving a recent result of Lu and Peng. We conjecture that this bound is still not optimal, and obtain some partial results towards the optimal bound.",
      "comment": "4 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2014-09-28T02:12:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cop number",
      "optimal bound",
      "short paper",
      "partial results",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1312.7555W"
    }
  }
}