2022/10/21 by Alon, Yahav, Krivelevich, Michael
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2210.11770
We prove that for every ε > 0 there is c0 such that if G∼ G(n,c/n), c≥ c0, then with high probability G can be covered by at most (1+ε)⋅ (1)/(2)ce-c ⋅ n vertex disjoint paths, which is essentially tight. This is equivalent to showing that, with high probability, at most (1+ε)⋅ (1)/(2)ce-c ⋅ n edges can be added to G to create a Hamiltonian graph.