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
    0 references
    0 references
    0 references
    0 references
    algorithm connect
    0 references
    random digraph
    0 references
    strongly connected
    0 references
    0 references
    0 references
    0 references
    0 references