Name
Title | ||
|---|---|---|
The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1017/S096354830400611X | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
direct analogy,degree sequence,large fan-in,bow-tie digraph,random digraph,connected component,sparse random digraph,extinction probability,strong connectivity,full characterization,strongly connected component | Discrete mathematics,Combinatorics,Vertex (geometry),Giant component,Degree (graph theory),Strongly connected component,Mathematics,Digraph,Extinction,Branching (version control) | Journal |
Volume | Issue | ISSN |
13 | 3 | 0963-5483 |
Citations | PageRank | References |
16 | 1.80 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 287 | 30.73 |
| Alan M. Frieze | 2 | 4837 | 787.00 |