Skip to main content
Article
Highly Connected Random Geometric Graphs
Discrete Applied Mathematics
  • Paul Balister, University of Memphis
  • Béla Bollobás, University of Memphis
  • Amites Sarkar, Western Washington University
  • Mark Walters, University of London
Document Type
Article
Publication Date
1-28-2009
Keywords
  • Random geometric graph,
  • Connectivity,
  • Poisson process
Disciplines
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.

DOI
http://dx.doi.org/10.1016/j.dam.2008.03.001
Required Publisher's Statement

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

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
Citation Information
Paul Balister, Béla Bollobás, Amites Sarkar and Mark Walters. "Highly Connected Random Geometric Graphs" Discrete Applied Mathematics Vol. 157 Iss. 2 (2009) p. 309 - 320
Available at: http://works.bepress.com/amites_sarkar/4/