Pósa's conjecture on the square of a Hamiltonian cycle

About 12 years old · traced to

Let GG be a graph on nn vertices. The square of a Hamiltonian cycle is Cn2C_n^2, where vertices at cyclic distance at most two are adjacent. Pósa's conjecture. If

δ(G)≥2n3,\delta(G)\geq\frac{2n}{3},

then Cn2⊆GC_n^2\subseteq G. This conjecture would significantly strengthen the Corrádi–Hajnal theorem and implies the relevant degree-two case of the Bollobás–Eldridge–Catlin conjecture.

References

Primary source

Louis DeBiasio, Safi Faizullah and Imdadullah Khan, “Ore-degree threshold for the square of a Hamiltonian cycle”, arXiv:1403.0776 (2015).

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.