Ore-degree threshold for the square of a Hamiltonian cycle

MaRDI QIDQ5173167zbMATH OpenFDO

Authors Louis DeBiasio, Safi Faizullah, Imdadullah Khan

Publication date 9 February 2015

Full work available at URL https://arxiv.org/abs/1403.0776, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2563/0.html

zbMATH Keywords

cycle powersHamiltonian cycleOre-degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45)

Abstract: A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n/2 contains a Hamiltonian cycle. In 1963, P'osa conjectured that every graph with minimum degree at least 2n/3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the Dirac's theorem by proving that every graph with $deg(u)+deg(v)geqn$ for every $uvotinE(G)$ contains a Hamiltonian cycle. Recently, Ch^au proved an Ore-type version of P'osa's conjecture for graphs on $ngeq{n}_0$ vertices using the regularity--blow-up method; consequently the $n_0$ is very large (involving a tower function). Here we present another proof that avoids the use of the regularity lemma. Aside from the fact that our proof holds for much smaller $n_0$, we believe that our method of proof will be of independent interest.

Recommendations

• An Ore-type theorem on Hamiltonian square cycles
• On degree sequences forcing the square of a Hamilton cycle
• On a degree sequence analogue of Pósa's conjecture
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• On the square of a Hamiltonian cycle in dense graphs

Cited in

(8)

• On degree sequences forcing the square of a Hamilton cycle
• Embedding graphs having Ore-degree at most five
• On a degree sequence analogue of Pósa's conjecture
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• An Ore-type theorem on Hamiltonian square cycles
• A dirac-type theorem for squares of graphs
• The Square of a Hamiltonian Cycle
• How to avoid using the regularity Lemma: Pósa's conjecture revisited

This page was built for publication: Ore-degree threshold for the square of a Hamiltonian cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5173167)