The size of the giant component of a random graph with a given degree sequence

被引:515
作者
Molloy, M [1 ]
Reed, B
机构
[1] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada
[2] Univ Paris 06, CNRS, Equipe Combinatoire, Paris, France
关键词
D O I
10.1017/S0963548398003526
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Given a sequence of nonnegative real numbers lambda(0),lambda(1),.. that sum to 1, we consider a random graph having approximately lambda(i)n vertices of degree i. In [12] the authors essentially show that if Sigma i(i - 2)lambda(i) > 0 then the graph a.s. has a giant component, while if Sigma i(i - 2)lambda(i) < 0 then a.s. all components in the graph are small. In this paper we analyse the size of the giant component in the former case, and the structure of the graph formed by deleting that component. We determine epsilon,lambda(0)',lambda(1)'... such that a.s. the giant component, C, has epsilon n + o(n) vertices, and the structure of the graph remaining after deleting C is basically that of a random graph with n' = n - \C\ vertices, and with lambda(i)'n' of them of degree i.
引用
收藏
页码:295 / 305
页数:11
相关论文
共 14 条