The size of the largest strongly connected component of a random digraph with a given degree sequence

被引：52

作者：

Cooper, C ^{[1
]}

Frieze, A

机构：

[1] Univ London Goldsmiths Coll, Dept Math & Comp Sci, London SW14 6NW, England

[2] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2004年 / 13卷 / 03期

关键词：

D O I：

10.1017/S096354830400611X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give results on the strong connectivity for spaces of sparse random digraphs specified by degree sequence. A full characterization is provided, in probability, of the fan-in and fan-out of all vertices including the number of vertices with small (o(n)) and large (cn) fan-in or fan-out. We also give the size of the giant strongly connected component, if any, and the structure of the bow-tie digraph induced by the vertices with large fan-in or fan-out. Our results follow a direct analogy of the extinction probabilities of classical branching processes.

引用

页码：319 / 337

页数：19

共 16 条

[1] Aiello W., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P171, DOI 10.1145/335305.335326
[2] [Anonymous], 1990, Random Struct. Algorithms, DOI [DOI 10.1002/RSA.3240010305, 10.1002/rsa.3240010305]
[3] 2 MOMENTS SUFFICE FOR POISSON APPROXIMATIONS - THE CHEN-STEIN METHOD
ARRATIA, R
GOLDSTEIN, L
GORDON, L
[J]. ANNALS OF PROBABILITY, 1989, 17 (01) : 9 - 25
[4] THE EVOLUTION OF RANDOM GRAPHS
BOLLOBAS, B
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1984, 286 (01) : 257 - 274
[5] Bollobas B., 2001, Random Graphs, V21
[6] Bollobas B., 1980, Eur. J. Comb., V1, P311, DOI [DOI 10.1016/S0195-6698(80)80030-8, 10.1016/S0195-6698(80)80030-8]
[7] Graph structure in the Web
Broder, A
Kumar, R
Maghoul, F
Raghavan, P
Rajagopalan, S
Stata, R
Tomkins, A
Wiener, J
[J]. COMPUTER NETWORKS-THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNICATIONS NETWORKING, 2000, 33 (1-6): : 309 - 320
[8] COOPER C, 2002, UNPUB RSA
[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

← 1 2 →