Teoriya Veroyatnostei i ee Primeneniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Teor. Veroyatnost. i Primenen.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Full-text PDF (646 kB) Citations (9)
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, Volume 20, Issue 2, Pages 401–409
DOI: https://doi.org/10.1137/1120047
Bibliographic databases:
Document Type: Article
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Lis75}
\by V.~A.~Liskovets
\paper On the number of vertices of a~random acyclic digraph
\jour Teor. Veroyatnost. i Primenen.
\yr 1975
\vol 20
\issue 2
\pages 412--420
\mathnet{http://mi.mathnet.ru/tvp3153}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=380925}
\zmath{https://zbmath.org/?q=an:0362.60030}
\transl
\jour Theory Probab. Appl.
\yr 1976
\vol 20
\issue 2
\pages 401--409
\crossref{https://doi.org/10.1137/1120047}
Linking options:
  • https://www.mathnet.ru/eng/tvp3153
  • https://www.mathnet.ru/eng/tvp/v20/i2/p412
  • This publication is cited in the following 9 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Теория вероятностей и ее применения Theory of Probability and its Applications
    Statistics & downloads:
    Abstract page:257
    Full-text PDF :133
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024