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 RegularityBlowup method and the Connecting Absorbing
method.
Original language  English 

Pages (fromto)  383437 
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
Treglown, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils