The cover time of random geometric graphs

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 $\Upsilon_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\ne v,\,w\in D(v,r)\}$ . Let $G(d,r,n),\,d\geq 3$ be a random geometric graph. Let $C_G$ denote the cover time of a simple random walk on G . Let $c>1$ be constant, and let $r=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies$$C_G\sim c\log \left({{c}\over{c-1}}\right)n\log n.$$ © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011