When are random graphs connected
From MaRDI portal
(Redirected from When are random graphs connected)
A random graph on the positive integers is formed by independently including each possible edge \(\{\) i,j\(\}\) with a probability \(p_{ij}\). Two models are considered, one with \(p_{ij}\) depending on \(| i- j|\) only, and one with \(p_{ij}=\max \{1,\lambda /\max \{i,j\}\}\) for some \(\lambda >0\). Necessary and sufficient conditions on the \(p_{ij}\) are given that imply that the random graph is connected with probability 1.
Recommendations
- Connectedness of certain random graphs
- On the connectedness of a random graph
- scientific article; zbMATH DE number 3904623
- Connectedness of graphs generated by a random d-process
- scientific article; zbMATH DE number 3999977
- Proper connection number of random graphs
- Connections in randomly oriented graphs
- On the strength of connectedness of a random graph
- \(k\)-connectivity in random graphs
- Sets that are connected in two random graphs
Cited in
(32)- On a method for random graphs
- Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses
- MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
- On the evolution of islands
- When is NEPS of graphs connected?
- On the connectivity of configuration graphs
- Enlargement of subgraphs of infinite graphs by Bernoulli percolation
- Harry Kesten's work in probability theory
- Continuous-time independent edge-Markovian random graph process
- Asymptotic equivalence and contiguity of some random graphs
- Connection probabilities in Poisson random graphs with uniformly bounded edges
- On the connectedness of a random graph
- Long paths and connectivity in 1-independent random graphs
- A power law for connectedness of some random graphs at the critical point
- scientific article; zbMATH DE number 15665 (Why is no real title available?)
- scientific article; zbMATH DE number 124392 (Why is no real title available?)
- The phase transition in the uniformly grown random graph has infinite order
- scientific article; zbMATH DE number 2091895 (Why is no real title available?)
- On the connectivity of a random interval graph
- The impact of edge correlations in random networks
- Truncation of long-range percolation models with squarenon-summable interactions
- scientific article; zbMATH DE number 3218580 (Why is no real title available?)
- Critical window for connectivity in the configuration model
- Random Graphs
- On connectivity in random graph models with limited dependencies
- Connecting probability for random bounded-range one-dimensional network
- Dynamic random graphs with vertex removal
- Large random graphs in pseudo-metric spaces
- Bounds on probability of connectedness of a random graph
- Connectedness of certain random graphs
- Critical values in a long-range percolation on spaces like fractals
- Bounds on probability of group connectedness of a random graph
This page was built for publication: When are random graphs connected
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1119947)