{
  "id": "2005.10849",
  "version": "v1",
  "published": "2020-05-21T18:09:02.000Z",
  "updated": "2020-05-21T18:09:02.000Z",
  "title": "On the cop number of graphs of high girth",
  "authors": [
    "Peter Bradshaw",
    "Seyyed Aliasghar Hosseini",
    "Bojan Mohar",
    "Ladislav Stacho"
  ],
  "comment": "18 pages, 1 figure",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We establish a lower bound for the cop number of graphs of high girth in terms of the minimum degree, and more generally, in terms of a certain growth condition. We show, in particular, that the cop number of any graph with girth $g$ and minimum degree $\\delta$ is at least $\\tfrac{1}{g}(\\delta - 1)^{\\lfloor \\frac{g-1}{4}\\rfloor}$. We establish similar results for directed graphs. While exposing several reasons for conjecturing that the exponent $\\tfrac{1}{4}g$ in this lower bound cannot be improved to $(\\tfrac{1}{4}+\\varepsilon)g$, we are also able to prove that it cannot be increased beyond $\\frac{3}{8}g$. This is established by considering a certain family of Ramanujan graphs. In our proof of this bound, we also show that the \"weak\" Meyniel's conjecture holds for expander graph families of bounded degree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-05-21T18:09:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57"
    ],
    "keywords": [
      "cop number",
      "high girth",
      "lower bound",
      "minimum degree",
      "expander graph families"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}