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

Teor. Veroyatnost. i Primenen., 1974 Volume 19, Issue 4, Pages 740–754 (Mi tvp3977)

This article is cited in 8 papers

On extreme metric parameters of a random graph, I

Yu. D. Burtin

Leningrad

Abstract: A random graph $G_n(t)$ is considered such that the edge between every pair of its vertices exists with the probability $p=1-e^{-t}$, $0<t<\infty$, independently from the other edges.
Let $L=[\log_{nt}n]$ be the integer part of $\log_{nt}n$. Then, uniformly in $t\ge(c_n \log n)/n$ $(\lim_{n\to\infty}c_n=\infty)$,
$$ \lim_{n\to\infty}\mathbf P(L+l\le d(G_n(t))\le L+2)=1, $$
where $d(G_n(t))$ denotes the diameter of the random graph. Thus the limit distribution of the diameter may be concentrated at at most two points.
Analogous propositions hold true for the radius and the cycle index of the random graph $G_n(t)$.

Received: 01.03.1973


 English version:
Theory of Probability and its Applications, 1975, 19:4, 710–725

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024