The connectivity of a graph on uniform points on [0,1] |
| |
Authors: | Martin J. B. Appel Ralph P. Russo |
| |
Affiliation: | a Capital Markets Operations, MGIC, Milwaukee, WI 53202, USA b Department of Statistics and Actuarial Science, University of Iowa, Iowa City, IA 52242, USA |
| |
Abstract: | A random graph Gn(x) is constructed on independent random points U1,…,Un distributed uniformly on [0,1]d, d1, 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. The connectivity distance cn, the smallest x for which Gn(x) is connected, is shown to satisfy For d2, the random graph Gn(x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: cn/dn→1, a.s., as n→∞, where dn is the largest nearest-neighbor link, the smallest x for which Gn(x) has no isolated vertices. |
| |
Keywords: | Random graph Connectivity Connectivity distance Largest nearest-neighbor link Random minimal spanning tree Geometric probability |
本文献已被 ScienceDirect 等数据库收录! |
|