2-factors with k cycles in Hamiltonian graphs
METADATA ONLY
Loading...
Author / Producer
Date
2020-09
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
A well known generalisation of Dirac's theorem states that if a graph G on n≥4k vertices has minimum degree at least n/2 then G contains a 2-factor consisting of exactly k cycles. This is easily seen to be tight in terms of the bound on the minimum degree. However, if one assumes in addition that G is Hamiltonian it has been conjectured that the bound on the minimum degree may be relaxed. This was indeed shown to be true by Sárközy. In subsequent papers, the minimum degree bound has been improved, most recently to (2/5+ε)n by DeBiasio, Ferrara, and Morris. On the other hand no lower bounds close to this are known, and all papers on this topic ask whether the minimum degree needs to be linear. We answer this question, by showing that the required minimum degree for large Hamiltonian graphs to have a 2-factor consisting of a fixed number of cycles is sublinear in n. © 2020 Elsevier Inc. All rights reserved.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
144
Pages / Article No.
150 - 166
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Hamiltonian cycles; 2-factors; Dirac thresholds
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
175573 - Extremal problems in combinatorics (SNF)