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 “ordinary ” random geometric graph, provided that pinr2 − 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−1 lnn), provided that pnr2 ≥ n1/2+ε and p < 1 − ε for some ε> 0