Connectivity threshold of Bluetooth graphs

DOI10.1002/RSA.20459MaRDI QIDQ2874082zbMATH OpenOpenAlexFDO

Authors Nicolas Broutin, Nicolas Fraiman, Luc Devroye, Gábor Lugosi

Publication date 28 January 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.0351

zbMATH Keywords

connectivitydiameterpercolationrandom geometric graphspanning ratio

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study the connectivity properties of random Bluetooth graphs that model certain "ad hoc" wireless networks. The graphs are obtained as "irrigation subgraphs" of the well-known random geometric graph model. There are two parameters that control the model: the radius $r$ that determines the "visible neighbors" of each node and the number of edges $c$ that each node is allowed to send to these. The randomness comes from the underlying distribution of data points in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters $r,c$ and completely characterize the connectivity threshold (in $c$) for values of $r$ close the critical value for connectivity in the underlying random geometric graph.

Recommendations

• Connectivity of sparse Bluetooth networks
• On the Expansion and Diameter of Bluetooth-Like Topologies
• On the expansion and diameter of bluetooth-like topologies
• Connectivity of random k-nearest-neighbour graphs
• Thresholding random geometric graph properties motivated by ad hoc sensor networks

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Compressions and isoperimetric inequalities
• Hamilton cycles in 3-out
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• On the connectivity of random m-orientable graphs and digraphs
• On the existence of Hamiltonian cycles in a class of random graphs
• Percolation
• Probability Inequalities for Sums of Bounded Random Variables
• Random Geometric Graphs
• Surface order large deviations for high-density percolation
• The critical probability of bond percolation on the square lattice equals 1/2
• The longest edge of the random minimal spanning tree

Cited in

(5)

• On the expansion and diameter of bluetooth-like topologies
• Connectivity of sparse Bluetooth networks
• Connectivity of soft random geometric graphs
• Randomized near-neighbor graphs, giant components and applications in data science
• On the Expansion and Diameter of Bluetooth-Like Topologies

This page was built for publication: Connectivity threshold of Bluetooth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874082)