{
  "id": "2008.03173",
  "version": "v1",
  "published": "2020-08-07T13:32:01.000Z",
  "updated": "2020-08-07T13:32:01.000Z",
  "title": "Hamiltonian cycles and 1-factors in 5-regular graphs",
  "authors": [
    "Nico Van Cleemput",
    "Carol T. Zamfirescu"
  ],
  "comment": "27 pages, 13 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "It is proven that for any integer $g \\ge 0$ and $k \\in \\{ 0, \\ldots, 10 \\}$, there exist infinitely many 5-regular graphs of genus $g$ containing a 1-factorisation with exactly $k$ pairs of 1-factors that are perfect, i.e. form a hamiltonian cycle. For $g = 0$, this settles a problem of Kotzig from 1964. Motivated by Kotzig and Labelle's \"marriage\" operation, we discuss two gluing techniques aimed at producing graphs of high cyclic edge-connectivity. We prove that there exist infinitely many planar 5-connected 5-regular graphs in which every 1-factorisation has zero perfect pairs. On the other hand, by the Four Colour Theorem and a result of Brinkmann and the first author, every planar 4-connected 5-regular graph satisfying a condition on its hamiltonian cycles has a linear number of 1-factorisations each containing at least one perfect pair. We also prove that every planar 5-connected 5-regular graph satisfying a stronger condition contains a 1-factorisation with at most nine perfect pairs, whence, every such graph admitting a 1-factorisation with ten perfect pairs has at least two edge-Kempe equivalence classes. The paper concludes with further results on edge-Kempe equivalence classes in planar 5-regular graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-08-07T13:32:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C45",
      "05C07",
      "05C10",
      "05C15",
      "05C70"
    ],
    "keywords": [
      "hamiltonian cycle",
      "edge-kempe equivalence classes",
      "high cyclic edge-connectivity",
      "zero perfect pairs",
      "stronger condition contains"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}