Random geometric graph, Connectivity, Poisson process
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.
Discrete Applied Mathematics
Required Publisher's Statement
Published by Elsevier
Balister, Paul; Bollobás, Béla; Sarkar, Amites; and Walters, Mark, "Highly Connected Random Geometric Graphs" (2009). Mathematics. 84.
Subjects - Topical (LCSH)
Random graphs; Graph connectivity; Poisson processes
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.