Edge-disjoint Hamilton cycles under a bipartite-hole condition

Abstract

In 2017, McDiarmid and Yolov introduced the bipartite-hole-number $\widetildeα(G)$ and proved that $δ(G)\ge \widetildeα(G)$ forces a Hamilton cycle. They also gave a sufficient condition for packing edge-disjoint Hamilton cycles, and asked whether this condition is sharp or can be relaxed. For integers $a,k\ge 2$, let $f(a,k)$ be the least integer $d$ such that every graph $G$ on at least three vertices with $\widetildeα(G)\le a$ and $δ(G)\ge d$ contains $k$ pairwise edge-disjoint Hamilton cycles. We prove that $f(a,k)=Θ\left(a+k+\frac{ak}{\log(k+2)}\right).$ The upper bound uses a deletion lemma for the bipartite-hole-number together with the McDiarmid--Yolov Hamiltonicity theorem and a greedy packing argument. The lower bound is obtained from three extremal constructions, the logarithmic one using a sparse random auxiliary graph with no prescribed bipartite hole.

Disclosure

“n bipartite holes leads to sharper non-uniform packing criteria. Acknowledgments This work was supported by the Science and Technology Commission of Shanghai Municipality (No. 25ZR1402474). Declaration on the use of AI The authors used generative AI tools to assist in discussing proof strategies, checking proofs, and im- proving exposition. References [1] N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed., Wiley, Hoboken, 2016. [2] B. Bollobás, Random Graphs, 2nd ed., Ca”

PDF page 8

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:34:05.733Z

Structural counts