Skip to Main content Skip to Navigation
Journal articles

Ore-degree threshold for the square of a Hamiltonian cycle

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) ≥ n for every uv =2 E(G) contains a Hamiltonian cycle. Recently, Chˆau proved an Ore-type version of P´osa’s conjecture for graphs on n ≥ n0 vertices using the regularity–blow-up method; consequently the n0 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 n0, we believe that our method of proof will be of independent interest.
Document type :
Journal articles
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-01218404
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, October 21, 2015 - 10:22:28 AM
Last modification on : Wednesday, August 21, 2019 - 11:52:02 AM
Long-term archiving on: : Friday, April 28, 2017 - 8:13:18 AM

File

dmtcs-17-1-2.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01218404, version 1

Collections

Citation

Louis Debiasio, Safi Faizullah, Imdadullah Khan. Ore-degree threshold for the square of a Hamiltonian cycle. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.13--32. ⟨hal-01218404⟩

Share

Metrics

Record views

233

Files downloads

1346