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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.13--32
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01218404
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 21 octobre 2015 - 10:22:28
Dernière modification le : jeudi 28 décembre 2017 - 13:58:02
Document(s) archivé(s) le : vendredi 28 avril 2017 - 08:13:18

Fichier

dmtcs-17-1-2.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

175

Téléchargements de fichiers

216