On k-Connectivity for a Geometric Random Graph

By Mathew D. Penrose.

For n points uniformly randomly distributed on the unit cube in d dimensions, with d > 1, let rn, (respectively sn) denote the minimum r at which the graph, obtained by adding an edge between each pair of points distant at most r apart, is k-connected (respectively, has minimum degree k). Then rn = sn with probability approaching 1 as n tends to infinity.

Random Structures and Algorithms 15, 145-164 (1999).