##
**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 **lim**_{n ––> +oo} Pr(c_{i}(\Gamma_{n,N(n)}) = r) = 1-\exp(-e^{-2\alpha}/r!), where i = 1,2,3 and c_{1}(G) denotes the minimal number of all edges starting from a single point in a given graph G, c_{2}(G) or c_{3} (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 c_{2}(G) = n-1).

**Reviewer: ** K.Culik

**Classif.: ** * 05C40 Connectivity

05C80 Random graphs

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag