2-factors with k cycles in Hamiltonian graphs

Matija Bucić, Erik Jahn, Alexey Pokrovskiy, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)150-166
Number of pages17
JournalJournal of Combinatorial Theory. Series B
Volume144
DOIs
StatePublished - Sep 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • 2-factors
  • Dirac thresholds
  • Hamiltonian cycles

Fingerprint

Dive into the research topics of '2-factors with k cycles in Hamiltonian graphs'. Together they form a unique fingerprint.

Cite this