*banner
 

Connectivity of Random Geometric Graph
P. Balister, B. Bollobas, A. Sarkar

Citation
P. Balister, B. Bollobas, A. Sarkar. "Connectivity of Random Geometric Graph". 2004 Combinatorics, Graph Theory and Computing Conference, 2004.

Abstract
Suppose n radio transceivers are scattered at random over a desert. Each radio is able to establish a direct two-way connection with the k radios nearest to it. In addition, messages can be routed via intermediate radios, so that a message can be sent indirectly from radio S to radio T through a series of radios S(1), S(2), S(3), ... , S(n)=T, each one having a direct connection to its predecessor. How large does k have to be to ensure that any two radios can communicate (directly or indirectly) with each other? To model the situation, we construct a random geometric graph G(n,k) by joining each point of a Poisson process in the square to its k nearest neighbors. Recently, Xue and Kumar proved that if k=0.074 log n then the probability that G(n,k) is connected tends to zero as n tends to infinity, while if k=5.1774 log n then the probability that G(n,k) is connected tends to one as n tends to ï‚¥. They conjectured that the threshold for connectivity is k=log n. In this paper we improve these lower and upper bounds to k=0.3043 log n and k=0.5139 log n respectively, disproving this conjecture. We also prove bounds for some generalizations of this problem.

Electronic downloads

Citation formats  
  • HTML
    P. Balister, B. Bollobas, A. Sarkar. <a
    href="http://chess.eecs.berkeley.edu/pubs/762.html"
    >Connectivity of Random Geometric Graph</a>, 2004
    Combinatorics, Graph Theory and Computing Conference, 2004.
  • Plain text
    P. Balister, B. Bollobas, A. Sarkar. "Connectivity of
    Random Geometric Graph". 2004 Combinatorics, Graph
    Theory and Computing Conference, 2004.
  • BibTeX
    @inproceedings{BalisterBollobasSarkar04_ConnectivityOfRandomGeometricGraph,
        author = {P. Balister and B. Bollobas and A. Sarkar},
        title = {Connectivity of Random Geometric Graph},
        booktitle = {2004 Combinatorics, Graph Theory and Computing
                  Conference},
        year = {2004},
        abstract = { Suppose n radio transceivers are scattered at
                  random over a desert. Each radio is able to
                  establish a direct two-way connection with the k
                  radios nearest to it. In addition, messages can be
                  routed via intermediate radios, so that a message
                  can be sent indirectly from radio S to radio T
                  through a series of radios S(1), S(2), S(3), ... ,
                  S(n)=T, each one having a direct connection to its
                  predecessor. How large does k have to be to ensure
                  that any two radios can communicate (directly or
                  indirectly) with each other? To model the
                  situation, we construct a random geometric graph
                  G(n,k) by joining each point of a Poisson process
                  in the square to its k nearest neighbors.
                  Recently, Xue and Kumar proved that if k=0.074 log
                  n then the probability that G(n,k) is connected
                  tends to zero as n tends to infinity, while if
                  k=5.1774 log n then the probability that G(n,k) is
                  connected tends to one as n tends to ï‚¥. They
                  conjectured that the threshold for connectivity is
                  k=log n. In this paper we improve these lower and
                  upper bounds to k=0.3043 log n and k=0.5139 log n
                  respectively, disproving this conjecture. We also
                  prove bounds for some generalizations of this
                  problem.},
        URL = {http://chess.eecs.berkeley.edu/pubs/762.html}
    }
    

Posted by Christopher Brooks on 4 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess