k-connectivity in random undirected graphs

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Spirakis, PG

Published Date

  • January 1, 1985

Published In

Volume / Issue

  • 54 / 2

Start / End Page

  • 181 - 191

International Standard Serial Number (ISSN)

  • 0012-365X

Digital Object Identifier (DOI)

  • 10.1016/0012-365X(85)90079-2

Citation Source

  • Scopus