2013/12/27 by Muller, Tobias, Pralat, Pawel
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1312.7170
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 πn r2 - ln n → ∞ (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-2 p-1 ln n), provided that p n r2 ≥ n1/2+\eps and p < 1-\eps for some \eps>0.