Publications [#237099] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Spirakis, PG, k-connectivity in random undirected graphs, Discrete Mathematics, vol. 54 no. 2 (January, 1985), pp. 181-191, Elsevier BV, ISSN 0012-365X [pdf], [doi]
   (last updated on 2026/01/16)

   Abstract:
   This paper concerns vertex connectivity in random graphs. We present results bounding the cardinality of the biggest k-block in random graphs of the Gn,p model, for any constant value of k. Our results extend the work of Erdös and Rényi and Karp and Tarjan. We prove here that Gn,p, with p≥ c n, has a giant k-block almost surely, for any constant k>0. The distribution of the size of the giant k-block is examined. We provide bounds on this distribution which are very nearly tight. We furthermore prove here that the cardinality of the biggest k-block is greater than n-log n, with probability at least 1-1/(n²log n), for p≥ c n and c>k+3. © 1985.