## 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-2Reif, 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.

## 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