The acquaintance time of (percolated) random geometric graphs

In this paper, we study the acquaintance time AC(G)AC(G) defined for a connected graph GG. We focus on G(n,r,p)G(n,r,p), a random subgraph of a random geometric graph in which nn vertices are chosen uniformly at random and independently from [0,1]2[0,1]2, and two vertices are adjacent with probability pp if the Euclidean distance between them is at most rr. We present asymptotic results for the acquaintance time of G(n,r,p)G(n,r,p) for a wide range of p=p(n)p=p(n) and r=r(n)r=r(n). In particular, we show that with high probability AC(G)=Θ(r−2)AC(G)=Θ(r−2) for G∈G(n,r,1)G∈G(n,r,1), the usual random geometric graph, provided that πnr2−lnn→∞πnr2−lnn→∞ (that is, above the connectivity threshold). For the percolated random geometric graph G∈G(n,r,p)G∈G(n,r,p), we show that with high probability AC(G)=Θ(r−2p−1lnn)AC(G)=Θ(r−2p−1lnn), provided that pnr2≥n1/2+εpnr2≥n1/2+ε and p<1−εp<1−ε for some ε>0ε>0.