RUS  ENG
Full version
JOURNALS // Teoriya Veroyatnostei i ee Primeneniya // Archive

Teor. Veroyatnost. i Primenen., 1970 Volume 15, Issue 1, Pages 56–68 (Mi tvp1549)

This article is cited 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, 15:1, 55–67

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024