The acquaintance time of (percolated) random geometric graphs

Abstract

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)=Θ(r-2) for G∈G(n,r,1), the usual random geometric graph, provided that πnr2-lnn→∞ (that is, above the connectivity threshold). For the percolated random geometric graph G∈G(n,r,p), we show that with high probability AC(G)=Θ(r-2p-1lnn), provided that pnr2≥n1/2+ε and p<1-ε for some ε>0.