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

• http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBMQFjAA&url=http%3A%2F%2Fwww.ims.nus.edu.sg%2FPrograms%2Frandomgraphs%2Ffil

• 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.