Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  103.16302
Autor:  Erdös, Pál; Rényi, Alfréd
Title:  On the strength of connectedness of a random graph (In English)
Source:  Acta Math. Acad. Sci. Hung. 12, 261-267 (1961).
Review:  Using the notation of the paper reviewed above the following theorem is proved: If N(n) = 1/2 n log n+ 1/2 r n log log n+\alpha n+o(n), where \alpha is a real constant and r a non-negative integer, then

limn ––> +oo Pr(ci(\Gamman,N(n)) = r) = 1-\exp(-e-2\alpha/r!),

where i = 1,2,3 and c1(G) denotes the minimal number of all edges starting from a single point in a given graph G, c2(G) or c3 (G) denotes the least number k such that by deleting k appropriately chosen points or edges the resulting graph is disconected (if G is complete with n points one puts c2(G) = n-1).
Reviewer:  K.Culik
Classif.:  * 05C40 Connectivity
                   05C80 Random graphs
Index Words:  topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page