#### 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

#### DOI

http://dx.doi.org/10.1239/aap/1113402397

#### 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 Faculty Publications*. 83.

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

#### Subjects - Topical (LCSH)

Random graphs; Graph connectivity; Poisson processes

#### Genre/Form

articles

#### Type

Text

#### Rights

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.

#### 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