|
|||||
|
|
Highly connected random geometric graphs |
|
| Authors: | Paul Balister Amites Sarkar Mark Walters |
| Institution: | a University of Memphis, Department of Mathematics, Dunn Hall, 3725 Norriswood, Memphis, TN 38152, USA b DPMMS, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB, United Kingdom c Department of Mathematics, Western Washington University, 516 High Street, Bellingham, WA 98225, USA d School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, United Kingdom |
| 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. |
| Keywords: | Random geometric graph Connectivity Poisson process |
| 本文献已被 ScienceDirect 等数据库收录！ | |