Imagine one generates some form of random graph (e.g. a random geometric graph) and via simulation, calculates the probability that there exists an edge-wise path between all vertices in the graph as a function of the number of vertices and/or the allowed edge lengths in an area of fixed size (e.g. a square or circle). Is there a technical term for this "connected graph" threshold? How does this relate to to the percolation threshold where we look for a giant connected component?

## 1 Answer

$\begingroup$
$\endgroup$

0
The technical term is just that: "connectivity threshold" or "threshold for connectivity".

In general, the connectivity threshold and the giant component threshold are different. Take, for example, the percolation thresholds on the path $P_{n/2} + K_{n/2}$. In this case, the giant component threshold is $p = 1/n$ but the connectivity threshold is $p = 1$.