Projects per year
Abstract
A famous conjecture of Posa from 1962 asserts that every graph on n vertices and
with minimum degree at least 2n/3 contains the square of a Hamilton cycle. The conjecture was
proven for large graphs in 1996 by Komlos, Sarkozy and Szemeredi [27]. In this paper we prove
a degree sequence version of P´osa’s conjecture: Given any η > 0, every graph G of sufficiently
large order n contains the square of a Hamilton cycle if its degree sequence d1 ≤ · · · ≤ dn satisfies
di ≥ (1/3 + η)n + i for all i ≤ n/3. The degree sequence condition here is asymptotically best
possible. Our approach uses a hybrid of the Regularity-Blow-up method and the Connecting Absorbing
method.
Original language | English |
---|---|
Pages (from-to) | 383-437 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 31 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2 Mar 2017 |
Keywords
- Hamilton cycle
- Pósa's conjecture
- regularity method
Fingerprint
Dive into the research topics of 'On degree sequences forcing the square of a Hamilton cycle'. Together they form a unique fingerprint.Projects
- 1 Finished
-
EPSRC Fellowship: Dr Andrew Treglown - Independence in groups, graphs and the integers
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils