The Minimum Vertex Degree of a Graph on Uniform Points in [0, 1]d
- 1 September 1997
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 29 (3) , 582-594
- https://doi.org/10.2307/1428077
Abstract
This article continues an investigation begun in [2]. A random graph Gn(x) is constructed on independent random points U1, · ··, Un 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 dn, the smallest x such that Gn(x) has no vertices of degree zero, is shown to satisfy Series and sequence criteria on edge distances {xn} 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.Keywords
This publication has 5 references indexed in Scilit:
- The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]dAdvances in Applied Probability, 1997
- The limit distribution of the largest nearest-neighbour link in the unit d-cubeJournal of Applied Probability, 1989
- Boundary domination and the distribution of the largest nearest-neighbor link in higher dimensionsJournal of Applied Probability, 1986
- Graph TheoryPublished by Springer Nature ,1979
- Central Limit Theorems for Empirical MeasuresThe Annals of Probability, 1978