#### Document Type

Article

#### Publication Date

2005

#### Keywords

Random geometric graph, connectivity, Poisson process

#### Abstract

Let *P* be a Poisson process of intensity one in a square *S*_{n} of area *n*. We construct a random geometric graph *G*_{n,k} by joining each point of *P*to its *k* ≡ *k*(*n*) nearest neighbours. Recently, Xue and Kumar proved that if *k* ≤ 0.074log*n* then the probability that *G*_{n,k} is connected tends to 0 as *n* → ∞ while, if *k* ≥ 5.1774log*n*, then the probability that *G*_{n,k} is connected tends to 1 as *n* → ∞. They conjectured that the threshold for connectivity is *k* = (1 + *o*(1))log*n*. In this paper we improve these lower and upper bounds to 0.3043log*n* and 0.5139log*n*, respectively, disproving this conjecture. We also establish lower and upper bounds of 0.7209log*n* and 0.9967log*n* for the directed version of this problem. A related question concerns coverage. With *G*_{n,k} as above, we surround each vertex by the smallest (closed) disc containing its *k* nearest neighbours. We prove that if *k* ≤ 0.7209log*n* then the probability that these discs cover *S*_{n} tends to 0 as *n* → ∞ while, if *k* ≥ 0.9967log*n*, then the probability that the discs cover *S*_{n} tends to 1 as *n* → ∞.

#### Publication Title

Advances in Applied Probability

#### Volume

37

#### Issue

1

#### First Page

1

#### Last Page

24

#### Required Publisher's Statement

Published by Project Euclid

doi:10.1239/aap/1113402397

#### Recommended Citation

Balister, Paul; Bollobás, Béla; Sarkar, Amites; and Walters, Mark, "Connectivity of Random k-Nearest-Neighbor Graphs" (2005). *Mathematics*. 83.

https://cedar.wwu.edu/math_facpubs/83

#### Language

English

#### Format

application/pdf

## Comments

This is the authors' post refereed version of the article. Here is a link to the publisher's version: http://projecteuclid.org/euclid.aap/1113402397