{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}