{
  "id": "2211.08105",
  "version": "v1",
  "published": "2022-11-15T12:51:17.000Z",
  "updated": "2022-11-15T12:51:17.000Z",
  "title": "Few hamiltonian cycles in graphs with one or two vertex degrees",
  "authors": [
    "Jan Goedgebeur",
    "Jorik Jooken",
    "On-Hei Solomon Lo",
    "Ben Seamone",
    "Carol T. Zamfirescu"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Experim. Math. 27 (2018) 426-430]. Thereafter, we use the Lov\\'asz Local Lemma to extend Thomassen's independent dominating set method. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen. Motivated by an observation of Aldred and Thomassen, we prove that for every $\\kappa \\in \\{ 2, 3 \\}$ and any positive integer $k$, there are infinitely many non-regular graphs of connectivity $\\kappa$ containing exactly one hamiltonian cycle and in which every vertex has degree $3$ or $2k$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-15T12:51:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamiltonian cycle",
      "vertex degrees",
      "thomassens independent dominating set method",
      "complement haythorpes computational enumerative results",
      "extend thomassens independent dominating set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}