**Originator(s):**
Paul Seymour, Princeton University

**Conjecture:**
A graph of order *n* with minimum degree at least *(k/(k+1))n*
contains the *k*th power of a Hamiltonian cycle.
(Pósa conjectured the special case for *k=2*.)

**Background:**
Dirac showed that minimum degree at least *n/2* in an *n*-vertex
graph forces a Hamiltonian cycle. Higher minimum degree should force
denser structures. The *k*th *power* of a graph *G* is the graph
obtained from *G* by adding edges to make vertices separated by distance
at most *k* in *G* adjacent.

**Partial results:**
The conjecture has been proved for sufficiently large *n*,
in [1] for *k=2* and in [3] and [4] for general *k*. The proof uses
the regularity lemma and the "blow-up lemma" [2]. There were several earlier
weaker results.

**References:**

[1] Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre
Random Structures Algorithms 9 (1996), no. 1-2, 193--211; MR 99f:05073

[2] Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre
Combinatorica 17 (1997), no. 1, 109--123; MR 99b:05083

[3] Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre
Proof of the Seymour conjecture for large graphs.
Ann. Comb. 2 (1998), no. 1, 43--60; MR 2000h:05144

[4]
Komlós, János(1-RTG); Sárközy, Gábor N.(1-WPI-C); Szemerédi, Endre(1-RTG-C)
On the Pósa-Seymour conjecture. (English. English summary)
J. Graph Theory 29 (1998), no. 3, 167--176. MR 99g:05125
05C45 (05C35)

**Keywords:**