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 [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: