Louis DeBiasio ; Safi Faizullah ; Imdadullah Khan - Ore-degree threshold for the square of a Hamiltonian cycle

dmtcs:2127 - Discrete Mathematics & Theoretical Computer Science, February 2, 2015, Vol. 17 no. 1 - https://doi.org/10.46298/dmtcs.2127
Ore-degree threshold for the square of a Hamiltonian cycle

Authors: Louis DeBiasio ; Safi Faizullah 1,2; Imdadullah Khan ORCID-iD3

  • 1 Hewlett-Packard
  • 2 Department of Computer Science [Rutgers]
  • 3 Department of Computer Science [Lahore]]

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.


Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: February 2, 2015
Submitted on: March 4, 2014
Keywords: Ore-degree,Hamiltonian cycle,cycle powers,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1007/bf01895727
  • 10.1007/bf01895727
On the maximal number of independent circuits in a graph

Consultation statistics

This page has been seen 290 times.
This article's PDF has been downloaded 465 times.