Seymour's kth-power Hamiltonian Conjecture

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.

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


Back to Index Page Link to Glossary