2-factors with k cycles in Hamiltonian graphs

DOI10.1016/J.JCTB.2020.02.002MaRDI QIDQ777484zbMATH OpenOpenAlexFDO

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

Publication date 7 July 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.09729

zbMATH Keywords

2-factorsDirac thresholdsHamiltonian cycles

Mathematics Subject Classification ID

Vertex degrees (05C07) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: A well known generalisation of Dirac's theorem states that if a graph $G$ on $nge4k$ 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+varepsilon)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.$

Recommendations

• Improved degree conditions for 2-factors with k cycles in Hamiltonian graphs
• On 2-factors with \(k\) components
• A note on 2-factors with two components
• scientific article; zbMATH DE number 1743771
• Degree conditions for 2-factors

Cites work

• A note on 2-factors with two components
• Degree conditions for 2-factors
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• scientific article; zbMATH DE number 2192128 (Why is no real title available?)
• Improved degree conditions for 2-factors with k cycles in Hamiltonian graphs
• On 2-factors with \(k\) components
• On extremal problems of graphs and generalized graphs
• Robustness of graph properties
• Some Theorems on Abstract Graphs
• Updating the hamiltonian problem—A survey

Cited in

(14)

• Maximal sets of 2-factors and Hamiltonian cycles
• 2-factors and Hamiltonicity
• Disjoint cycles and \(2\)-factors with Fan-type condition in a graph
• On factor-invariant graphs with two cycles
• On 2-factor Hamiltonian regular bipartite graphs
• A note on 2-factors with two components
• Betwixt and between 2-factor Hamiltonian and perfect-matching-Hamiltonian graphs
• scientific article; zbMATH DE number 5130728 (Why is no real title available?)
• Improved degree conditions for 2-factors with k cycles in Hamiltonian graphs
• Hamiltonian ?-factors in graphs
• A \([k,k+1]\)-factor containing a given Hamiltonian cycle
• A \([k,k+1]\)-factor containing a given Hamiltonian cycle
• On partitioning a bipartite graph into a specified number of cycles and degree sum conditions for two vertices of distance three
• On 2-factors with \(k\) components

This page was built for publication: 2-factors with \(k\) cycles in Hamiltonian graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777484)