The acquaintance time of (percolated) random geometric graphs

Tobias Muller, Pawel Pralat

Published 2013-12-27Version 1

In this paper, we study the acquaintance time $\AC(G)$ defined for a connected graph $G$. We focus on $\G(n,r,p)$, a random subgraph of a random geometric graph in which $n$ vertices are chosen uniformly at random and independently from $[0,1]^2$, and two vertices are adjacent with probability $p$ if the Euclidean distance between them is at most $r$. We present asymptotic results for the acquaintance time of $\G(n,r,p)$ for a wide range of $p=p(n)$ and $r=r(n)$. In particular, we show that with high probability $\AC(G) = \Theta(r^{-2})$ for $G \in \G(n,r,1)$, the "ordinary" random geometric graph, provided that $\pi n r^2 - \ln n \to \infty$ (that is, above the connectivity threshold). For the percolated random geometric graph $G \in \G(n,r,p)$, we show that with high probability $\AC(G) = \Theta(r^{-2} p^{-1} \ln n)$, provided that $p n r^2 \geq n^{1/2+\eps}$ and $p < 1-\eps$ for some $\eps>0$.