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

About 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

Primary source

Jorik Jooken, “Improved asymptotic upper bounds for the minimum number of pairwise distinct longest cycles in regular graphs”, arXiv:2310.17469 (2023).

Additional 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.

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.