← All problems

Häggkvist's Hamiltonicity conjecture for oriented graphs

3 years old · traced to

Let DD be an oriented graph on nn vertices. Define

δ∗(D)=δ(D)+δ+(D)+δ−(D).\delta^*(D)=\delta(D)+\delta^+(D)+\delta^-(D).

Häggkvist's conjecture. Every oriented graph DD with

δ∗(D)>3n−32\delta^*(D)>\frac{3n-3}{2}

is Hamiltonian.

This conjecture was verified approximately by Kelly: the weaker condition δ∗(D)≥(3/2+o(1))n\delta^*(D)\geq (3/2+o(1))n guarantees Hamiltonicity. The exact threshold stated here is therefore resolved according to the supplied status evidence.

References

2 papers in this index state this conjecture (2023–2024). The statement above is taken from the most recent of them; the others are arXiv:2311.05505.

Source: Jia Zhou, Zhilan Wang and Jin Yan, “The generalizations of Hamiltonian in oriented graphs”, arXiv:2402.03878 (2024).

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.