The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected (Q914707)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected |
scientific article |
Statements
The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected (English)
0 references
1990
0 references
In the present paper, the authors solve an open problem concerning the connectivity of a particular model of random digraph, raised by B. Bollobas. They investigate a random digraph \(D_{\alpha,\beta}(n)\) with vertex set \(V_ n=\{1,2,...,n\}\) in which each vertex \(v\in V_ n\) independently chooses \(\alpha\) random arcs entering v and \(\beta\) random arcs leaving v and they compute the limiting probability that \(D_{\alpha,\beta}(n)\) is strongly connected as n tends to infinity. They acknowledge the insight of W. Fernandez in pointing out the fact that the limit could not be 1.
0 references
algorithm connect
0 references
random digraph
0 references
strongly connected
0 references