×

On the Pósa-Seymour conjecture. (English) Zbl 0919.05042

Summary: Paul Seymour conjectured that any graph \(G\) of order \(n\) and minimum degree at least \({k\over k+1}n\) contains the \(k\)th power of a Hamilton cycle. We prove the following approximate version. For any \(\varepsilon>0\) and positive integer \(k\), there is an \(n_0\) such that, if \(G\) has order \(n\geq n_0\) and minimum degree at least \(\left({k\over k+1}+\varepsilon\right)n\), then \(G\) contains the \(k\)th power of a Hamilton cycle.

MSC:

05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI