On the strength of connectedness of a random graph. (English) Zbl 0103.16302

Using the notation of the paper reviewed above the following theorem is proved: If \(N(n) ={1 \over 2} n \log n + {1 \over 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 \to +\infty} \text{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.Čulik


05C40 Connectivity
05C80 Random graphs (graph-theoretic aspects)


Full Text: DOI


[1] D. König,Theorie der endlichen und unendlichen Graphen (Leipzig, 1936). · JFM 62.0654.05
[2] C. Berge,Théorie des graphes et ses applications (Paris, 1958).
[3] L. R. Ford andD. R. Fulkerson, Maximal flow through a network,Canadian Journal of Math.,8 (1956), p. 399. · Zbl 0073.40203
[4] P. Erdos andA. Rényi, On random graphs. I,Publ. Math. Debrecen,6 (1959), pp. 290–297. · Zbl 0092.15705
[5] P. Erdos andA. Rényi, On the evolution of random graphs,Publ. Math. Inst. Hung. Acad. Sci.,5 (1960), pp. 17–61. · Zbl 0103.16301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.