On degree sequences forcing the square of a Hamilton cycle

Andrew Treglown, Katherine Staden

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
106 Downloads (Pure)

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 languageEnglish
Pages (from-to)383-437
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number1
DOIs
Publication statusPublished - 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.

Cite this