|
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
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
Linking options:
https://www.mathnet.ru/eng/tvp1549 https://www.mathnet.ru/eng/tvp/v15/i1/p56
|
Statistics & downloads: |
Abstract page: | 435 | Full-text PDF : | 278 |
|