{
  "id": "2104.10020",
  "version": "v1",
  "published": "2021-04-20T15:01:26.000Z",
  "updated": "2021-04-20T15:01:26.000Z",
  "title": "Regular graphs with few longest cycles",
  "authors": [
    "Carol T. Zamfirescu"
  ],
  "comment": "21 pages, 12 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant $c$ such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly $c$ hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput, and that it holds for 4-regular graphs of connectivity~2 with the constant $144 < c$, which we believe to be minimal among all hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every non-negative integer $k$ there is a 5-regular graph on $26 + 6k$ vertices with $2^{k+10} \\cdot 3^{k+3}$ hamiltonian cycles. We prove that for every $d \\ge 3$ there is an infinite family of hamiltonian 3-connected graphs with minimum degree $d$, with a bounded number of hamiltonian cycles. It is shown that if a 3-regular graph $G$ has a unique longest cycle $C$, at least two components of $G - E(C)$ have an odd number of vertices on $C$, and that there exist 3-regular graphs with exactly two such components.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-20T15:01:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C45",
      "05C07",
      "05C38",
      "05C10"
    ],
    "keywords": [
      "regular graphs",
      "hamiltonian cycles",
      "unique longest cycle",
      "infinite family",
      "odd number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}