Document Type

Article

Publication Date

1-28-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. We construct a random geometric graph Gn,k by joining each point of P to its k nearest neighbours. For many applications it is desirable that Gn,k is highly connected, that is, it remains connected even after the removal of a small number of its vertices. In this paper we relate the study of the s-connectivity of Gn,k to our previous work on the connectivity of Gn,k. Roughly speaking, we show that for s=o(logn), the threshold (in k) for s-connectivity is asymptotically the same as that for connectivity, so that, as we increase k, Gn,k becomes s-connected very shortly after it becomes connected.

Publication Title

Discrete Applied Mathematics

Volume

157

Issue

2

First Page

309

Last Page

320

DOI

http://dx.doi.org/10.1016/j.dam.2008.03.001

Required Publisher's Statement

Published by Elsevier

DOI: 10.1016/j.dam.2008.03.001

Comments

This is the authors' version of the article. Here is a link to the publisher's version: http://www.sciencedirect.com/science/article/pii/S0166218X08001236

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