On a degree sequence analogue of Pósa’s conjecture

Andrew Treglown, Katherine Staden

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)
133 Downloads (Pure)

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 [Komlós, J., G.N. Sárközy and E. Szemerédi, On the square of a Hamiltonian cycle in dense graphs, Random Structures and Algorithms 9 (1996), 193–211]. We prove a degree sequence version of Pósa'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
Title of host publicationElectronic Notes in Discrete Mathematics
Pages233-241
Volume49
DOIs
Publication statusPublished - 12 Nov 2015

Keywords

  • degree sequence
  • square of Hamilton cycle
  • Pósa's conjecture
  • regularity lemma

Fingerprint

Dive into the research topics of 'On a degree sequence analogue of Pósa’s conjecture'. Together they form a unique fingerprint.

Cite this