Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T10:02:35.606Z Has data issue: false hasContentIssue false

The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence

Published online by Cambridge University Press:  28 April 2004

COLIN COOPER
Affiliation:
Department of Mathematical and Computing Sciences, Goldsmiths College, London SW14 6NW, UK (e-mail: cooper@dcs.kcl.ac.uk)
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, USA (e-mail: alan@random.math.cmu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2004 Cambridge University Press