This article is cited 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

 English version: Theory of Probability and its Applications, 1976, 20:2, 401–409

Bibliographic databases:

• 
•