The connectivity threshold for dense graphs
2021
Consider a random graph model where there is an underlying simple graph G = (V, E), and each edge is sampled independently with probability p ∈ [0, 1]. What is the smallest value of p such that the resulting graph Gp is connected with constant probability? This is a well-studied question for special classes of graphs, such as complete graphs and hypercubes. For instance, when G is the complete graph, we want the connectivity threshold for the Erdős-Rényi G(n, p) model: here the answer is known to be [EQUATION]. However, the problem is not well-understood for more general graph classes.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI