On the number of hamilton cycles in a random graph
On the number of hamilton cycles in a random graph
复制标题
关于随机图中的哈密尔顿循环数
DOI：
10.1002/jgt.3190130608
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
C. Cooper;A. Frieze
设一个随机图G，从n个孤立的顶点开始，通过逐个添加随机边来构造。我们证明，当n趋于无穷时，概率趋于1，当G第一次具有最小二阶时，对于任何固定的λ >0，它至少有（log n）个不同的汉密尔顿循环。
Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n) distinct hamilton cycles for any fixed ϵ>0.