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 条
  • [1] ALON N, 1992, PROBABILISTIC METHOD
  • [2] [Anonymous], RANDOM STRUCT ALGORI
  • [3] Azuma K, 1967, TOHOKU MATH J, V19, P357, DOI DOI 10.2748/TMJ/1178243286
  • [4] Bekessy A., 1972, Studia Scientiarum Mathematicarum Hungarica, V7, P343
  • [5] ASYMPTOTIC NUMBER OF LABELED GRAPHS WITH GIVEN DEGREE SEQUENCES
    BENDER, EA
    CANFIELD, ER
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 24 (03) : 296 - 307
  • [6] Billingsley P., 1986, PROBABILITY MEASURE
  • [7] THE EVOLUTION OF RANDOM GRAPHS
    BOLLOBAS, B
    [J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1984, 286 (01) : 257 - 274
  • [8] Bollobas B, 1980, EUR J COMBINAT, V1, P311
  • [9] ERDOS P, 1960, B INT STATIST INST, V38, P343
  • [10] THE BIRTH OF THE GIANT COMPONENT
    JANSON, S
    KNUTH, DE
    LUCZAK, T
    PITTEL, B
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1993, 4 (03) : 233 - 358