Connectivity of random k-nearest-neighbour graphs

DOI10.1239/aap/1113402397zbMath1079.05086OpenAlexW2056986231MaRDI QIDQ4676423

Béla Bollobás, Mark Walters, Paul N. Balister, Amites Sarkar

Publication date: 3 May 2005

Published in: Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1239/aap/1113402397

zbMATH Keywords

Poisson processrandom geometric graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Percolation (82B43) Zero-one laws (60F20) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55)

Related Items

Sharpness in the k-Nearest-Neighbours Random Geometric Graph Model, Degree distributions in \(AB\) random geometric graphs, Limit behaviors of random connected graphs driven by a Poisson process, Bootstrap percolation in random geometric graphs, Small components in \(k\)-nearest neighbour graphs, Randomized near-neighbor graphs, giant components and applications in data science, The distant-2 chromatic number of random proximity and random geometric graphs, Hamilton cycles in random geometric graphs, On the connectivity and diameter of small-world networks, On covering by translates of a set, Highly connected random geometric graphs, A critical constant for the k nearest-neighbour model, A New Random Graph Model with Self-Optimizing Nodes: Connectivity and Diameter, Modeling limited attention in opinion dynamics by topological interactions, Consensus of flocks under \(M\)-nearest-neighbor rules

Cites Work

• Unnamed Item
• Edge-isoperimetric inequalities in the grid
• The longest edge of the random minimal spanning tree
• A clustering procedure based on the comparison between the \(k\) nearest neighbors graph and the minimal spanning tree.
• Continuum percolation with steps in an annulus
• Efficient measurement of the percolation threshold for fully penetrable discs
• Random Plane Networks
• Random Geometric Graphs
• Continuum Percolation