← All problems

Haythorpe's lower-bound conjecture for Hamiltonian cycles in regular graphs

10 years old · traced to

Let rr and nn be integers with r≥5r\geq 5 and n≥r+3n\geq r+3, and let GG be a Hamiltonian rr-regular graph on nn vertices. Haythorpe's conjecture. The graph GG has at least

(r−1)2((r−2)!)nr+1(r-1)^2 ((r-2)!)^{\frac{n}{r+1}}

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

Never refreshed

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.