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, 1970, Volume 15, Issue 1, Pages 56–68 (Mi tvp1549)  

This article is cited in 48 scientific papers (total in 48 papers)

On the probability of connectedness of a graph $\mathscr G_m(t)$

V. E. Stepanov

Moscow
Abstract: In the previous paper of the author, it was shown that the probability of connectedness $P_m(t)$ of a random graph $\mathscr G_m(t)$ tends to exp $(-e^{-x})$ as $m\to\infty$ and $t=(\ln m+x+o(1))/m$.
In the present paper, an asymptotic expression of probability $P_m(t)$ is found in a wider range. It is proved that
$$ P_m(t)=\biggl(1-\frac{mt}{e^{mt}-1}\biggr)(1-e^{-mt})^m(1+o(1)) $$
uniformly in $t$ as $m\to\infty$ and $mt\ge y_0>0$. Based on this result, we prove that the distribution of the number of vertices in the greatest component of the graph $\mathscr G_m(t)$ is asymptotically normal as $m\to\infty$ and $mt>1$.
Received: 17.03.1969
English version:
Theory of Probability and its Applications, 1970, Volume 15, Issue 1, Pages 55–67
DOI: https://doi.org/10.1137/1115004
Bibliographic databases:
Language: Russian
Citation: V. E. Stepanov, “On the probability of connectedness of a graph $\mathscr G_m(t)$”, Teor. Veroyatnost. i Primenen., 15:1 (1970), 56–68; Theory Probab. Appl., 15:1 (1970), 55–67
Citation in format AMSBIB
\Bibitem{Ste70}
\by V.~E.~Stepanov
\paper On the probability of connectedness of a~graph~$\mathscr G_m(t)$
\jour Teor. Veroyatnost. i Primenen.
\yr 1970
\vol 15
\issue 1
\pages 56--68
\mathnet{http://mi.mathnet.ru/tvp1549}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=MR0270406}
\zmath{https://zbmath.org/?q=an:0233.60006|0213.45805}
\transl
\jour Theory Probab. Appl.
\yr 1970
\vol 15
\issue 1
\pages 55--67
\crossref{https://doi.org/10.1137/1115004}
Linking options:
  • https://www.mathnet.ru/eng/tvp1549
  • https://www.mathnet.ru/eng/tvp/v15/i1/p56
  • This publication is cited in the following 48 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
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024