{
  "id": "2009.00693",
  "version": "v1",
  "published": "2020-09-01T20:55:33.000Z",
  "updated": "2020-09-01T20:55:33.000Z",
  "title": "Most Generalized Petersen graphs of girth 8 have cop number 4",
  "authors": [
    "Joy Morris",
    "Tigana Runte",
    "Adrian Skelton"
  ],
  "comment": "19 pages plus 11 pages of data in appendix. 11 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A generalized Petersen graph $GP(n,k)$ is a regular cubic graph on $2n$ vertices (the parameter $k$ is used to define some of the edges). It was previously shown (Ball et al., 2015) that the cop number of $GP(n,k)$ is at most $4$, for all permissible values of $n$ and $k$. In this paper we prove that the cop number of \"most\" generalized Petersen graphs is exactly $4$. More precisely, we show that unless $n$ and $k$ fall into certain specified categories, then the cop number of $GP(n,k)$ is $4$. The graphs to which our result applies all have girth $8$. In fact, our argument is slightly more general: we show that in any cubic graph of girth at least $8$, unless there exist two cycles of length $8$ whose intersection is a path of length $2$, then the cop number of the graph is at least $4$. Even more generally, in a graph of girth at least $9$ and minimum valency $\\delta$, the cop number is at least $\\delta+1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-01T20:55:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57",
      "91A46"
    ],
    "keywords": [
      "cop number",
      "generalized petersen graph",
      "regular cubic graph",
      "minimum valency",
      "result applies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}