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).