Western CEDAR

Title

Connectivity of Random k-Nearest-Neighbor Graphs

Authors

Paul Balister, University of Memphis
Béla Bollobás, University of Memphis
Amites Sarkar, Western Washington UniversityFollow
Mark Walters, Trinity College

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 Pto its k ≡ k(n) nearest neighbours. Recently, Xue and Kumar proved that if k ≤ 0.074logn then the probability that G_n,k is connected tends to 0 as n → ∞ while, if k ≥ 5.1774logn, 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))logn. In this paper we improve these lower and upper bounds to 0.3043logn and 0.5139logn, respectively, disproving this conjecture. We also establish lower and upper bounds of 0.7209logn and 0.9967logn 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.7209logn then the probability that these discs cover S_n tends to 0 as n → ∞ while, if k ≥ 0.9967logn, 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

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

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

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