Abstract:
A random graph Gn(t) is considered such that the edge between every pair of its vertices exists with the probability p=1−e−t, 0<t<∞, independently from the other edges.
Let L=[logntn] be the integer part of logntn. Then, uniformly in t⩾(cnlogn)/n(limn→∞cn=∞),
limn→∞P(L+l⩽d(Gn(t))⩽L+2)=1,
where d(Gn(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 Gn(t).
Citation:
Yu. D. Burtin, “On extreme metric parameters of a random graph, I”, Teor. Veroyatnost. i Primenen., 19:4 (1974), 740–754; Theory Probab. Appl., 19:4 (1975), 710–725
This publication is cited in the following 8 articles:
Tatyana Ivanovna Fedoryaeva, Proceedings of Academician O.B. Lupanov 14th International Scientific Seminar “Discrete Mathematics and Its Applications”, 2022, 21
T. I. Fedoryaeva, “On radius and typical properties of $n$-vertex graphs of given diameter”, Sib. elektron. matem. izv., 18:1 (2021), 345–357
Bernd Kreuter, Till Nierhoff, Lecture Notes in Computer Science, 1269, Randomization and Approximation Techniques in Computer Science, 1997, 43
E Bienenstock, “On the dimensionality of cortical graphs”, Journal of Physiology-Paris, 90:3-4 (1996), 251
M. B. Dale, Computer assisted vegetation analysis, 1991, 149
A. D. Korshunov, “The main properties of random graphs with a large number of vertices and edges”, Russian Math. Surveys, 40:1 (1985), 121–198
Y. D. Burtin, “On a simple formula for random mappings and its applications”, Journal of Applied Probability, 17:2 (1980), 403
Yu. D. Burtin, “On extreme metric characteristics of a random graph. II. Limit distributions”, Theory Probab. Appl., 20:1 (1975), 83–101