k-connectivity in random undirected graphs

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/(n2log n), for p≥ c n and c>k+3. © 1985.

Duke Scholars

Author John H. Reif Computer Science