The Minimum Vertex Degree of a Graph on Uniform Points in [0, 1]d

Abstract

This article continues an investigation begun in [2]. A random graph G_n(x) is constructed on independent random points U₁, · ··, U_n distributed uniformly on [0, 1]^d, d ≧ 1, in which two distinct such points are joined by an edge if the l_∞-distance between them is at most some prescribed value 0 < x < 1.Almost-sure asymptotic results are obtained for the convergence/divergence of the minimum vertex degree of the random graph, as the number n of points becomes large and the edge distance x is allowed to vary with n. The largest nearest neighbor link d_n, the smallest x such that G_n(x) has no vertices of degree zero, is shown to satisfy Series and sequence criteria on edge distances {x_n} are provided which guarantee the random graph to be complete, a.s. These criteria imply a.s. limiting behavior of the diameter of the vertex set.