Random geometric graph, Connectivity, Poisson process
Let P be a Poisson process of intensity 1 in a square Sn of area n. For a fixed integer k, join every point of P to its k nearest neighbours, creating an undirected random geometric graph Gn,k. We prove that there exists a critical constant ccrit such that, for c‹ccrit, Gn,⌊clogn⌋ is disconnected with probability tending to 1 as n →∞ and, for c‹ccrit, Gn,⌊clogn⌋ is connected with probability tending to 1 as n →∞. This answers a question posed in Balister et al. (2005).
Advances in Applied Probability
Required Publisher's Statement
Published by Project Euclid
Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. A critical constant for the k nearest-neighbour model. Adv. in Appl. Probab. 41 (2009), no. 1, 001--012. doi:10.1239/aap/1240319574. http://projecteuclid.org/euclid.aap/1240319574.
Subjects - Topical (LCSH)
Random graphs; Graph connectivity; Poisson processes
Copying of this document in whole or in part is allowable only for scholarly purposes. It is understood, however, that any copying or publication of this document for commercial purposes, or for financial gain, shall not be allowed without the author’s written permission.