|
Teoriya Veroyatnostei i ee Primeneniya, 1975, Volume 20, Issue 2, Pages 412–420
(Mi tvp3153)
|
|
|
|
This article is cited in 9 scientific papers (total in 9 papers)
Short Communications
On the number of vertices of a random acyclic digraph
V. A. Liskovets Minsk
Abstract:
An acyclic digraph is a digraph without directed circuits. Unlike the similar class of non-directed graphs which are called trees, random acyclic digraphs have been hardly studied. Here we are concerned with a rather simple property of them.
A vertex of a digraph is called maximal if there are no arcs entering it. Any finite non-empty acyclic digraph has a maximal vertex. Let $\xi_n$ be the number of maximal vertices in a graph chosen at random from the set of all acyclic digraphs without multiple arcs with $n$ given vertices. The main result provides the limit distribution of $\xi_n$ as $n\to\infty$: it is proved to be a discrete probability distribution with the generating function $\alpha(a(1-z))$ where
$$
\alpha(z)=\sum_{n=0}^\infty\frac{(-1)^nz^n}{n!2^{n(n-1)/2}}
$$
and $a$ is the least real root of $\alpha(z)=0,$ $a<1,5$. In particular, $\lim\mathbf M\xi_n=a$, $\lim\mathbf D\xi_n=a(1-a/2)$.
Received: 10.12.1973
Citation:
V. A. Liskovets, “On the number of vertices of a random acyclic digraph”, Teor. Veroyatnost. i Primenen., 20:2 (1975), 412–420; Theory Probab. Appl., 20:2 (1976), 401–409
Linking options:
https://www.mathnet.ru/eng/tvp3153 https://www.mathnet.ru/eng/tvp/v20/i2/p412
|
Statistics & downloads: |
Abstract page: | 257 | Full-text PDF : | 133 |
|