Ore-degree threshold for the square of a Hamiltonian cycle
Louis DeBiasio, Safi Faizullah, Imdadullah Khan
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ósa 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 ∉ E(G) contains a
Hamiltonian cycle. Recently, Châu proved an Ore-type version of
Pósa'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.
Full Text: PDF