On degree sequences forcing the square of a Hamilton cycle

Abstract

A famous conjecture of Pósa 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 Komlós, Sárközy and Szemerédi. In this paper we prove a degree sequence version of Pósa's conjecture: Given any $\eta >0$, every graph $G$ of sufficiently large order $n$ contains the square of a Hamilton cycle if its degree sequence $d_1\le \cdots \le d_n$ satisfies $d_i\ge (1/3+\eta )n+i$ for all $i\le 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.

arXiv comment52 pages, 5 figures, to appear in SIAM J. Discrete Math