The critical behavior of random digraphs
- 23 July 2009
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 35 (3) , 271-293
Abstract
We study the critical behavior of the random digraph D(n,p) for np = 1 + ε, where ε = ε(n) = o(1). We show that if ε3n →—∞, then a.a.s. D(n,p) consists of components which are either isolated vertices or directed cycles, each of size Op(|ε|−1). On the other hand, if ε3n →∞, then a.a.s. the structure of D(n,p) is dominated by the unique complex component of size (4 + o(1))ε2n, whereas all other components are of size Op(ε−1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009Keywords
This publication has 13 references indexed in Scilit:
- Cycles and Unicyclic Components in Random GraphsCombinatorics, Probability and Computing, 2003
- Random Graphs2001
- Random Graphs2000
- The birth of the giant componentRandom Structures & Algorithms, 1993
- Giant components in three-parameter random directed graphsAdvances in Applied Probability, 1992
- Cycles in a random graph near the critical pointRandom Structures & Algorithms, 1991
- Component behavior near the critical point of the random graph processRandom Structures & Algorithms, 1990
- The phase transition in the evolution of random digraphsJournal of Graph Theory, 1990
- The transitive closure of a random digraphRandom Structures & Algorithms, 1990
- The Evolution of Random GraphsTransactions of the American Mathematical Society, 1984