Random graph's Hamiltonicity is strongly tied to its minimum degree
Yahav AlonMichael Krivelevich
所有作者
Yahav AlonMichael Krivelevich
文献摘要
We show that the probability that a random graph G∼G(n,p) contains no
Hamilton cycle is (1+o(1))Pr(δ(G)<2) for all values of p=p(n). We
also prove an analogous result for perfect matchings.