Haythorpe's lower-bound conjecture for Hamiltonian cycles in regular graphs
Let and be integers with and , and let be a Hamiltonian -regular graph on vertices. Haythorpe's conjecture. The graph has at least
Hamiltonian cycles. The conjecture proposes an asymptotic lower bound matching the construction discussed in the source, while the paper explains that its upper-bound results disprove the conjecture in a strong asymptotic sense.
References
2 papers in this index state this conjecture (2016–2023). The statement above is taken from the most recent of them; the others are arXiv:1608.00713.
Status
- Refuted: Jan Goedgebeur, Jorik Jooken, and Carol T. Zamfirescu. Few hamiltonian cycles in graphs with one or two vertex degrees (Mathematics of Computation, 2024) https://doi.org/10.1090/mcom/3943
Source: Jorik Jooken, “Improved asymptotic upper bounds for the minimum number of pairwise distinct longest cycles in regular graphs”, arXiv:2310.17469 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.