2025/03/20 by Xinmin Hou, Hou, Xinmin, Zhi Yin +1 · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Spectral Theory in Mathematical Physics
paper · pdf · doi:10.48550/arxiv.2503.15950
openalex publication_date 2025/03/20 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
The cycle space C(G) of a graph G is defined as the linear space spanned by all cycles in G. For an integer k≥ 3, let Ck (G) denote the subspace of C(G) generated by the cycles of length exactly k. A graph G on n vertices is called Hamilton-generated if Cn (G) = C(G), meaning every cycle in G is a symmetric difference of some Hamilton cycles of G. %A necessary condition for this property is that n must be odd. Heinig (European J. Combin., 2014) showed that for any σ>0 and sufficiently large odd n, every n-vertex graph with minimum degree (1+ σ)n/2 is Hamilton-generated. He further posed the question that whether the minimum degree requirement could be lowered to the Dirac threshold n/2. Recent progress by Christoph, Nenadov, and Petrova~(arXiv:2402.01447) reduced the minimum degree condition to n/2 + C for some large constant C. In this paper, we resolve Heinig's problem completely by proving that for sufficiently large odd n, every Hamilton-connected graph G on n vertices with minimum degree at least (n-1)/2 is Hamilton-generated. Moreover, this result is tight for the minimum degree and the Hamilton-connected condition. The proof relies on the parity-switcher technique introduced by Christoph, et al in their recent work, as well as a classification lemma that strengthens a previous result by Krivelevich, Lee, and Sudakov~(Trans. Amer. Math. Soc., 2014).