How many random edges make a graph hamiltonian?
How many random edges make a graph hamiltonian?
复制标题
有多少条随机边使图具有哈密顿性？
DOI：
--
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
Eli Shamir
中科院分区：
文献类型：
--
作者：
Eli Shamir
在随机图空间Gn，p的标度中，图性质Q的一个阈值是Q的渐近概率从0跳到1的ap带.我们找到了一个尖锐的阈值的属性有一个哈密顿路径。
A threshold for a graph propertyQ in the scale of random graph spacesGn,p is ap-band across which the asymptotic probability ofQ jumps from 0 to 1. We locate a sharp threshold for the property of having a hamiltonian path.