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.
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
Full Text: DOI arXiv