Journal article icon

Journal article

On degree sequences forcing the square of a Hamilton cycle

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 [Random Structures Algorithms, 9 (1996) pp. 193-211]. In this paper we prove a degree sequence version of Posa'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&l...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1137/15M1033101

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Treglown, A More by this author
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
SIAM Journal on Discrete Mathematics Journal website
Volume:
31
Issue:
1
Pages:
383-437
Publication date:
2017-03-02
Acceptance date:
2016-11-23
DOI:
EISSN:
1095-7146
ISSN:
0895-4801
Pubs id:
pubs:820641
URN:
uri:4468ee48-43ac-43e0-9c83-2fc1c3572c9a
UUID:
uuid:4468ee48-43ac-43e0-9c83-2fc1c3572c9a
Local pid:
pubs:820641

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP