k-connectivity in random undirected graphs
type: Item
instance of: scholarly article
title: k-connectivity in random undirected graphs
zbMATH Open document ID: 0567.05036
DOI: 10.1016/0012-365X(85)90079-2
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: It is shown that a random graph \(G_{n,p}\) of Erdős-Renyi type, with \(p\geq c/n\), has a giant k-block almost surely, for any constant \(k>0\). Bounds are given on the distribution of the size of the giant k-block for \(p\geq c\) log n/n.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60F15
zbMATH DE Number: 3904624
zbMATH Keywords: probability of connectivity
zbMATH Keywords: random k-blocks
zbMATH Keywords: random graph
zbMATH Keywords: giant k-block
author: J. Reif
author: P. G. Spirakis
MaRDI profile type: Publication
cites work: Q3267900
cites work: Q3286850
cites work: On the strength of connectedness of a random graph
cites work: Q4085109
cites work: k-Blocks and Ultrablocks in Graphs
cites work: A structural characterization of planar combinatorial graphs
cites work: Q3241504
full work available at URL: 0012-365x(85)90079-2
OpenAlex ID: W2053661482
Recommended article: \(k\)-connectivity in random graphs
Recommended article: Connectivity of random k-nearest-neighbour graphs
Recommended article: Q4217847
Recommended article: Connectivity of Inhomogeneous Random K-Out Graphs
Recommended article: On the Connectivity of Random k-th Nearest Neighbour Graphs
Recommended article: Connectedness of certain random graphs
Recommended article: On the connectedness of a random graph
Recommended article: Onk-leaf connectivity of a random graph
Recommended article: $k$ -Connectivity in Random Key Graphs With Unreliable Links
Recommended article: Q3682512
description: scientific article; zbMATH DE number 3904624