The cover time of random geometric graphs
Colin Cooper, ALAN M. FRIEZE · 2009
We study the cover time of random geometric graphs. Let I(d) = [0,1] d denote the unit torus in d dimensions. Let D(x,r) denote the ball (disc) of radius r. Let Υd be the volume of the unit ball D(0,1) in d dimensions. A random geometric graph G = G(d,r,n) in d dimensions is defined as follows: Sample n points V independently and uniformly at random from I(d). For each point x draw a ball D(x,r) of radius r about x. The vertex set V (G) = V and the edge set E(G) = {{v,w} : w ̸ = v, w ∈ D(v,r)}. Let G(d,r,n), d ≥ 3 be a random geometric graph. Let c> 1 be constant, and let r = (clog n/(Υdn)) 1/d. Then whp c CG ∼ clog n log n. c − 1 1