UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

2-factors with k cycles in Hamiltonian graphs

Bucic, M; Jahn, E; Pokrovskiy, A; Sudakov, B; (2020) 2-factors with k cycles in Hamiltonian graphs. Journal of Combinatorial Theory, Series B , 144 pp. 150-166. 10.1016/j.jctb.2020.02.002. Green open access

[img]
Preview
Text
1905.09729.pdf - Accepted version

Download (420kB) | Preview

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´ark¨ozy. 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.

Type: Article
Title: 2-factors with k cycles in Hamiltonian graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jctb.2020.02.002
Publisher version: https://doi.org/10.1016/j.jctb.2020.02.002
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Hamiltonian cycles, 2-factors, Dirac thresholds
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10112638
Downloads since deposit
5Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item