{
  "id": "2104.04898",
  "version": "v1",
  "published": "2021-04-11T02:17:12.000Z",
  "updated": "2021-04-11T02:17:12.000Z",
  "title": "Number of Hamiltonian cycles in planar triangulations",
  "authors": [
    "Xiaonan Liu",
    "Xingxing Yu"
  ],
  "comment": "20 pages, 2 figures, to be published in SIAM Journal on Discrete Mathematics",
  "categories": [
    "math.CO"
  ],
  "abstract": "Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. On the other hand, a recent result of Alahmadi, Aldred, and Thomassen states that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. In this paper, we consider 4-connected planar $n$-vertex triangulations $G$ that do not have too many separating 4-cycles or have minimum degree 5. We show that if $G$ has $O(n/{\\log}_2 n)$ separating 4-cycles then $G$ has $\\Omega(n^2)$ Hamiltonian cycles, and if $\\delta(G)\\ge 5$ then $G$ has $2^{\\Omega(n^{1/4})}$ Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a \"double wheel\" structure, providing further evidence to the above conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-11T02:17:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C30",
      "05C38",
      "05C40",
      "05C45"
    ],
    "keywords": [
      "hamiltonian cycles",
      "planar triangulation",
      "minimum degree",
      "thomassen states",
      "vertex triangulations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}