Skip to main content
Journal cover image

k-connectivity in random undirected graphs

Publication ,  Journal Article
Reif, JH; Spirakis, PG
Published in: Discrete Mathematics
January 1, 1985

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

Published In

Discrete Mathematics

DOI

ISSN

0012-365X

Publication Date

January 1, 1985

Volume

54

Issue

2

Start / End Page

181 / 191

Related Subject Headings

  • Computation Theory & Mathematics
  • 0802 Computation Theory and Mathematics
  • 0102 Applied Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Spirakis, P. G. (1985). k-connectivity in random undirected graphs. Discrete Mathematics, 54(2), 181–191. https://doi.org/10.1016/0012-365X(85)90079-2
Reif, J. H., and P. G. Spirakis. “k-connectivity in random undirected graphs.” Discrete Mathematics 54, no. 2 (January 1, 1985): 181–91. https://doi.org/10.1016/0012-365X(85)90079-2.
Reif JH, Spirakis PG. k-connectivity in random undirected graphs. Discrete Mathematics. 1985 Jan 1;54(2):181–91.
Reif, J. H., and P. G. Spirakis. “k-connectivity in random undirected graphs.” Discrete Mathematics, vol. 54, no. 2, Jan. 1985, pp. 181–91. Scopus, doi:10.1016/0012-365X(85)90079-2.
Reif JH, Spirakis PG. k-connectivity in random undirected graphs. Discrete Mathematics. 1985 Jan 1;54(2):181–191.
Journal cover image

Published In

Discrete Mathematics

DOI

ISSN

0012-365X

Publication Date

January 1, 1985

Volume

54

Issue

2

Start / End Page

181 / 191

Related Subject Headings

  • Computation Theory & Mathematics
  • 0802 Computation Theory and Mathematics
  • 0102 Applied Mathematics
  • 0101 Pure Mathematics