Document Type

Article

Publication Date

1-28-2009

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

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

Included in

Mathematics Commons

Share

COinS