论文标题
汉密尔顿的完成和稀疏随机图的路径覆盖数
Hamilton completion and the path cover number of sparse random graphs
论文作者
论文摘要
我们证明，每$ \ varepsilon> 0 $都有$ C_0 $，这样，如果$ g \ sim g（n，c/n）$，$ c \ ge c_0 $，那么使用高概率$ g $可以由$ $ g $覆盖，最多可以覆盖$（1+ \ varepsilon）\ cdot \ cdot \ cdot \ frac \ frac \ frac \ frac {1 n} n} n} c.2} ce^2} ce^c.路径本质上是紧密的。这相当于表明，只有高概率，最多最多$（1+ \ varepsilon）\ cdot \ frac {1} {2} ce^{ - c} \ cdot n $ edges可以添加到$ g $中以创建汉密尔顿图。
We prove that for every $\varepsilon > 0$ there is $c_0$ such that if $G\sim G(n,c/n)$, $c\ge c_0$, then with high probability $G$ can be covered by at most $(1+\varepsilon)\cdot \frac{1}{2}ce^{-c} \cdot n$ vertex disjoint paths, which is essentially tight. This is equivalent to showing that, with high probability, at most $(1+\varepsilon)\cdot \frac{1}{2}ce^{-c} \cdot n$ edges can be added to $G$ to create a Hamiltonian graph.
