Id: arxiv/2607.14881 Url: https://arxiv.org/abs/2607.14881 Tags: math.CO Score: 0 Title: Efficient Hamilton covers and linear arboricity of random graphs Domain: math.CO Source: arxiv Authors: Nemanja Draganić, Michael Krivelevich Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-16 Page: https://delphi.science/r/arxiv/2607.14881 A Hamilton cover of a graph is a collection of Hamilton cycles whose union contains all edges. Since each Hamilton cycle covers two edges at every vertex, every Hamilton cover has size at least $\lceil Δ(G)/2\rceil$. We prove that this lower bound is tight for binomial random graphs $G(n,p)$ throughout the widest possible range of edge probabilities: if $ω(n)\to\infty$ and \[ \frac{\log n+\log\log n+ω(n)}{n} \le p=p(n) \le 1-\frac{ω(n)}{n^{2}}, \] then $G\sim G(n,p)$ with high probability has a Hamilton cover of size $\left\lceil \frac{Δ(G)}{2}\right\rceil. $ The main new contribution is the…