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