k-connectivity in random undirected graphs
From MaRDI portal
K-connectivity in random undirected graphs
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.
Recommendations
- \(k\)-connectivity in random graphs
- Connectivity of random k-nearest-neighbour graphs
- scientific article; zbMATH DE number 1222330
- Connectivity of Inhomogeneous Random K-Out Graphs
- On the Connectivity of Random k-th Nearest Neighbour Graphs
- Connectedness of certain random graphs
- On the connectedness of a random graph
- Onk-leaf connectivity of a random graph
- <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Connectivity in Random Key Graphs With Unreliable Links
- scientific article; zbMATH DE number 3904623
Cites work
- A structural characterization of planar combinatorial graphs
- scientific article; zbMATH DE number 3126031 (Why is no real title available?)
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3504320 (Why is no real title available?)
- k-Blocks and Ultrablocks in Graphs
- On the strength of connectedness of a random graph
Cited in
(6)- \(k\)-connectivity in random graphs
- Note on directed proper connection number of a random graph
- A note on log-concave random graphs
- Finding maximum subgraphs with relatively large vertex connectivity
- Connectivity of random k-nearest-neighbour graphs
- On the Connectivity of Random k-th Nearest Neighbour Graphs
This page was built for publication: k-connectivity in random undirected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1059644)
