# zbMATH — the first resource for mathematics

Connectivity of sparse Bluetooth networks. (English) Zbl 1319.05114
Summary: Consider a random geometric graph defined on $$n$$ vertices uniformly distributedin the $$d$$-dimensional unit torus. Two vertices are connected if their distance is less than a “visibility radius” $$r_n$$. We consider Bluetooth networks that are locally sparsified random geometric graphs. Each vertex selects $$c$$ of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of $$n^{-(1-\delta)/d}$$ for some $$\delta > 0$$, then a constant value of $$c$$ is sufficient forthe graph to be connected, with high probability. It suffices to take $$c \geq \sqrt{(1+\epsilon)/\delta} + K$$ for any positive $$\epsilon$$ where $$K$$ is a constant depending on $$d$$ only. On the other hand, with $$c\leq \sqrt{(1-\epsilon)/\delta}$$, the graph is disconnected, with high probability.
##### MSC:
 05C80 Random graphs (graph-theoretic aspects) 05C40 Connectivity 68R10 Graph theory (including graph drawing) in computer science 68M10 Network design and communication in computer systems 60C05 Combinatorial probability
##### Keywords:
random geometric graph; connectivity; irrigation graph
Full Text: