Document Type

Article

Publication Date

2009

Keywords

Random geometric graph, Connectivity, Poisson process

Abstract

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).

Publication Title

Advances in Applied Probability

Volume

41

Issue

1

First Page

1

Last Page

12

DOI

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

Required Publisher's Statement

Published by Project Euclid

DOI:10.1239/aap/1240319574

Comments

This is the authors' version of the article. The publisher version is at: http://projecteuclid.org/euclid.aap/1240319574

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

Download

Included in

Mathematics Commons

COinS