Onk-connectivity for a geometric random graph

Abstract

For n points uniformly randomly distributed on the unit cube in d dimensions, with d≥2, let ρn (respectively, σn) 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 P[ρn=σn]→1 as n→∞. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 145–164, 1999