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
    []