McKay, Brendan D. On the shape of a random acyclic digraph. (English) Zbl 0702.05040 Math. Proc. Camb. Philos. Soc. 106, No. 3, 459-465 (1989). 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 Cited in 7 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C80 Random graphs (graph-theoretic aspects) Keywords:random; lengths; longest directed paths; labelled acyclic digraphs; asymptotically normally distributed PDFBibTeX XMLCite \textit{B. D. McKay}, Math. Proc. Camb. Philos. Soc. 106, No. 3, 459--465 (1989; Zbl 0702.05040) 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.