Hamilton cycles in random digraphs with minimum degree at least one
Colin CooperAlan Frieze
所有作者
Colin CooperAlan Frieze
文献摘要
We study the existence of a directed Hamilton cycle in random digraphs with m edges where we condition on minimum in- and out-degree at least one. Denote such a random graph by Dn,m(δ≥1). We prove that if m=2n(logn+2loglogn+cn) then n→∞limPr(Dn,m(δ≥1) is Hamiltonian)=⎩⎨⎧0e−e−c/41cn→−∞.cn→c.cn→∞.