The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected
type: Item
instance of: scholarly article
title: The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected
zbMATH Open document ID: 0702.05073
DOI: 10.1016/0095-8956(90)90134-L
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4150227
zbMATH Keywords: algorithm connect
zbMATH Keywords: random digraph
zbMATH Keywords: strongly connected
Wikidata QID: Q57401602
author: Colin Cooper
author: Alan Frieze
MaRDI profile type: Publication
cites work: Q3682518
cites work: On the connectivity of random m-orientable graphs and digraphs
cites work: Probability Inequalities for Sums of Bounded Random Variables
full work available at URL: 0095-8956(90)90134-l
OpenAlex ID: W1528229596
DBLP publication ID: journals/jct/CooperF90
description: scientific article; zbMATH DE number 4150227