The phase transition in the evolution of random digraphs
Author:
- 1 June 1990
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 14 (2) , 217-223
Abstract
Let \documentclass{article}\pagestyle{empty}$ \mathop {\rm D}\limits^ \to $ (n, M) denote a digraph chosen at random from the family of all digraphs on n vertices with M arcs. We shall prove that if M/n ≤ c < 1 and ω(n) → ∞, then with probability tending to 1 as n → ∞ all components of \documentclass{article}\pagestyle{empty}$ \mathop {\rm D}\limits^ \to $ (n, M) are smaller than ω(n), whereas when M/n ≥ c > 1 the largest component of \documentclass{article}\pagestyle{empty}$ \mathop {\rm D}\limits^ \to $ (n, M) is of the order n with probability 1 ‐ o(1).
Keywords
This publication has 2 references indexed in Scilit:
- The Evolution of Random GraphsTransactions of the American Mathematical Society, 1984
- Linear expected-time algorithms for connectivity problemsJournal of Algorithms, 1980