On 2 2 -factors of Hamiltonian graphs

Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg · 2026

Read On 2 2 -factors of Hamiltonian graphs by Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11288.txt.

Introduction

Espuny Díaz and three colleagues prove a result about Hamiltonian graphs, graphs that hold a cycle through every vertex. They show that any large enough such graph holds a 2-factor of exactly k cycles, for any k of two or more. This holds when its minimum degree is at least n to a power just below one. This is the first degree condition of its kind that is polynomially smaller than linear. Their methods also answer a question of Bucić, Jahn, Pokrovskiy and Sudakov.

Catalog record

CREATORAlberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67259
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11288

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On 2 2 -factors of Hamiltonian graphs Thanks: Alberto Espuny Díaz was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) through project no. 513704762. Bertille Granet was supported by the Australian Research Council grant DP240101048. Gal Kronenberg is supported by the Royal Commission for the Exhibition of 1851. Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg Abstract . Let k ≥ 2 k\geq 2 . We show that, for a sufficiently small ϵ > 0 \epsilon>0 , any sufficiently large n n -vertex Hamiltonian graph of minimum degree at least n 1 − ϵ n^{1-\epsilon} contains a 2 2 -factor consisting of exactly k k cycles. This is the first minimum-degree condition which is polynomially smaller than linear. Our methods yield an analogous result when the host graph is not required to contain a Hamilton cycle, but only a 2 2 -factor consisting of at most k k cycles; this answers a question of Bucić, Jahn, Pokrovskiy and Sudakov. 1. Introduction A Hamilton cycle in a graph G is a cycle that goes through every vertex of G , and a graph is Hamiltonian whenever it contains a Hamilton cycle. The problem of determining whether a graph is Hamiltonian is famously NP-complete [ 19 ] , and thus much effort has been devoted to finding simple sufficient conditions for Hamiltonicity. Perhaps the most famous of these is Dirac’s condition: his classical theorem from 1952 [ 12 ] states that every graph G on n\geq 3 vertices with minimum degree \delta(G)\geq n/2 contains a Hamilton cycle, and this minimum-degree condition is best possible, as can be seen by considering a slightly unbalanced complete bipartite graph. A 2 -factor of a graph G is a spanning 2 -regular subgraph. With this language, Dirac’s theorem provides an optimal minimum-degree condition for a graph to have a 2 -factor consisting of only one cycle. It is natural to wonder how the problem changes if, rather than exactly one cycle, we wish to find a 2 -factor consisting of exactly k cycles. This problem remains NP-complete [ 16 , p. 75] , and hence, again, it is natural to search for sufficient conditions for this property. In 1997, Brandt, Chen, Faudree, Gould and Lesniak 1997 extended Dirac’s theorem, showing that, for any positive integer k and provided n\geq 4k-1 (cf. [ 7 ] ), Dirac’s condition in fact ensures the existence of a 2 -factor consisting of exactly k cycles. (For several other sufficient conditions for this property, see, e.g., [ 2 , 6 , 14 , 7 , 8 , 25 , 9 ] ). This minimum-degree condition is again best possible. However, all graphs showing that this condition is tight are the same as for Dirac’s theorem; in particular, they are not Hamiltonian. This leads to the question of whether assuming that G is Hamiltonian could significantly reduce the sufficient minimum-degree condition for having a 2 -factor consisting of exactly k\geq 2 cycles. In 2005, Faudree, Gould, Jacobson, Lesniak and Saito 2005 considered this question and conjectured an affirmative answer, which they proved for the particular case that k=2 , showing that minimum degree \delta(G)\geq 5n/12+2 suffices for all n\geq 6 . Soon after, Sárközy 2008 proved the conjecture for all (fixed) k , reducing the lower bound of n/2 on the minimum degree by showing that there exists some \epsilon>0 such that, for every k\geq 2 and n sufficiently large, having minimum degree \delta(G)\geq(1/2-\epsilon)n suffices for an n -vertex Hamiltonian graph G to contain a 2 -factor consisting of k cycles. DeBiasio, Ferrara and Morris 2014 subsequently improved on the constant in the leading term of the minimum-degree condition, showing that, for every fixed \epsilon>0 and sufficiently large n , having minimum degree \delta(G)\geq(2/5+\epsilon)n suffices. More recently, Bucić, Jahn, Pokrovskiy and Sudakov 2020 substantially improved the previous results by showing that sublinear degrees suffice: for any k\geq 2 and \epsilon>0 , there exists an n_{0}\in\mathbb{N} such that every Hamiltonian graph on n\geq n_{0} vertices with \delta(G)\geq\epsilon n contains a 2 -factor consisting of exactly k cycles. Here we make new progress on this problem by providing the first polynomial-factor improvement on the sufficient minimum-degree condition for the existence of a 2 -factor consisting of exactly k cycles in a Hamiltonian graph. We also generalise previous results in two ways. First, we allow the number of cycles k to grow polynomially in n . Second, we do not in fact require G to contain a Hamilton cycle, but only a 2 -factor consisting of at most k cycles. This second generalisation answers a question of Bucić, Jahn, Pokrovskiy and Sudakov 2020 . Theorem 1 . For all 0<\delta\leq 1 , there exist \epsilon>0 and n_{0}\in\mathbb{N} such that the following holds. Let G be a graph on n\geq n_{0} vertices with minimum degree \delta(G)\geq n^{1-\epsilon} and let k\in\{1,\ldots,\lfloor n^{1-\delta}\rfloor\} . If G has a 2 -factor consisting of at most k cycles, then it contains a 2 -factor consisting of exactly k cycles. Bucić, Jahn, Pokrovskiy and Sudakov 2020 noted that, in fact, a careful analysis of their proof yields an (explicit) expression of the form \delta(G)\geq n/{\operatorname{poly}\log\log n} as a sufficient minimum-degree condition for having a 2 -factor consisting of exactly k cycles (for any fixed k and sufficiently large n ). However, they point out that their methods do not seem sufficient for improving the minimum-degree condition by a polynomial factor, like we achieve in Theorem 1 . Indeed, our approach for obtaining this improvement is very different from that in their paper. 2. Notation Given any x\in\mathbb{R} , we will denote [x]\coloneqq\{k\in\mathbb{Z}:1\leq k\leq x\} . To simplify the presentation, we will often write hierarchies to express the relationships between parameters in our statements. Formally, if we write that a statement holds for 0<a\ll b\leq 1 , we mean that for all b\in(0,1] there exists some a_{0}>0 such that, for all a\in(0,a_{0}] , the statement holds for this choice of a and b . This notation extends in the natural way to hierarchies which are longer or where one parameter depends on several others, with parameters being defined from right to left. When one of the parameters in a hierarchy is written as 1/k , the reader should interpret that k\in\mathbb{N} . For the sake of streamlining the presentation, we usually ignore rounding when this does not affect the argument. Some of our statements will be asymptotic in nature. When working with asymptotic statements in probabilistic settings, we will say that an event occurs asymptotically almost surely (a.a.s.) if the probability that it holds tends to 1 as n tends to infinity. Our graph-theoretic notation is standard. Let G be a graph with vertex set V(G) and edge set E(G) , and let E\subseteq E(G) be a set of edges and S,T\subseteq V(G) be disjoint sets of vertices. We write V(E)\coloneqq\bigcup_{e\in E}e . We denote by G\setminus E the graph on vertex set V(G) with edge set E(G)\setminus E . The subgraph of G induced by S , that is, the graph with vertex set S and edge set \{e\in E(G):e\subseteq S\} , is denoted by G[S] . We set G-S\coloneqq G[V(G)\setminus S] . We write e(G)\coloneqq|E(G)| . The

Read the complete text