Small components in k-nearest neighbour graphs

Details Small components in k-nearest neighbour graphs Small components in k-nearest neighbour graphs

2011-01-13

arxiv.org/abs/1101.2619v1

Mathematics

Probability

15 pages, 2 figures

Scientific paper

Let $G=G_{n,k}$ denote the graph formed by placing points in a square of area $n$ according to a Poisson process of density 1 and joining each point to its $k$ nearest neighbours. Balister, Bollob\'as, Sarkar and Walters proved that if $k<0.3043\log n$ then the probability that $G$ is connected tends to 0, whereas if $k>0.5139\log n$ then the probability that $G$ is connected tends to 1. We prove that, around the threshold for connectivity, all vertices near the boundary of the square are part of the (unique) giant component. This shows that arguments about the connectivity of $G$ do not need to consider `boundary' effects. We also improve the upper bound for the threshold for connectivity of $G$ to $k=0.4125\log n$.

Affiliated with

Also associated with

No associations

Rating

Small components in k-nearest neighbour graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small components in k-nearest neighbour graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small components in k-nearest neighbour graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67013