The diameter of sparse random graphs
The diameter of sparse random graphs
复制标题
DOI：
10.1006/aama.2001.0720
复制
发表时间：
2001-05-01
影响因子：
1.1
通讯作者：
Lu, LY
中科院分区：
文献类型：
--
作者：
Chung, F;Lu, LY
我们考虑一个随机图G（n，p）的直径为各种范围的p接近相变点的连通性。对于不连通图G，我们使用G的直径是其连通分支的最大直径的约定。证明了当np -->无穷大时，随机图G（n，p）的直径几乎必然接近logn/log（np）.此外，如果np/logn = c > 8，则C（n，p）的直径集中在两个值上。通常，如果np/log n = C > C-0，则直径集中在至多2 [1/c（0）]+4个值上。证明了当np > 3.6时，G（n，p）的直径几乎必然等于其巨分支的直径. (C)北京：科学出版社.
We consider the diameter of a random graph G(n, p) for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of random graph G(n, p) is close to logn/log (np) if np --> infinity. Moreover if np/log n = c > 8, then the diameter of C(n, p) is concentrated on two values. In general, if np/log n = C > C-0, the diameter is concentrated on at most 2 [1/c(0)] + 4 values. We also proved that the diameter of G(n, p) is almost surely equal to the diameter of its giant component if np > 3.6. (C) 2001 Academic Press.