×

On the shape of a random acyclic digraph. (English) Zbl 0702.05040

It is shown that the values of the lengths of the longest directed paths over all labelled acyclic digraphs on n nodes are asymptotically normally distributed with mean approximately 0.764334n and variance 0.145210n. Also, it is proved that the values of the numbers of sets \(V_ i(D)\) which have size k, \(k\geq 1\), over all labelled acyclic digraphs D on n nodes are asymptotically normally distributed with mean \(C_ kn\) and \(C_ k'n\) for positive constants \(C_ k\) and \(C_ k'\), where \(V_ i(D)\) denotes the set of nodes j such that the longest directed path from j to a node in the set of nodes of out-degree 0 has length i.
Reviewer: Wai-Kai Chen

MSC:

05C20 Directed graphs (digraphs), tournaments
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/0012-365X(73)90108-8 · Zbl 0258.05113
[2] Robinson, New Directions in Graph Theory pp 239– (1973)
[3] DOI: 10.1137/1120047 · Zbl 0362.60030
[4] DOI: 10.1016/0097-3165(73)90038-1 · Zbl 0242.05006
[5] DOI: 10.1063/1.451672
[6] DOI: 10.1016/0095-8956(88)90044-5 · Zbl 0654.05035
[7] DOI: 10.1007/BF02579404 · Zbl 0601.05025
[8] Liskovec, Teor. Veroyatnost. i Primenen. 20 pp 412– (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.