The diameter of sparse random graphs

被引:145
作者
Chung, F [1 ]
Lu, LY [1 ]
机构
[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
基金
美国国家科学基金会;
关键词
D O I
10.1006/aama.2001.0720
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:257 / 279
页数:23
相关论文
共 18 条
[1]  
Aiello W., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P171, DOI 10.1145/335305.335326
[2]  
AIELLO W, IN PRESS ADV APPL MA
[3]   Internet -: Diameter of the World-Wide Web [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 1999, 401 (6749) :130-131
[4]  
ALON N, 1992, PROBABALISTIC METHOD
[5]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[6]  
BOLLOBAS B, 1990, IEEE T INFORM THEORY, V36, P285
[7]  
Bollobas B., 1984, GRAPH THEORY COMBINA, P35
[8]  
Bollobas B., 2001, CAMBRIDGE STUDIES AD, V73
[9]  
Burtin J. D., 1974, TEOR VEROYA PRIMEN, V19, P740
[10]  
Burtin J. D., 1975, TEOR VEROYA PRIMEN, V20, P82