Originator(s): Paul Seymour, Princeton University
Conjecture: A graph of order n with minimum degree at least (k/(k+1))n contains the kth 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 kth 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  for k=2 and in  and  for general k. The proof uses the regularity lemma and the "blow-up lemma" . There were several earlier weaker results.
 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
 Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre Combinatorica 17 (1997), no. 1, 109--123; MR 99b:05083
 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
 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)