On the jump of the cover time in random geometric graphs

In this paper we study the cover time of the simple random walk on the giant component of supercritical $d$-dimensional random geometric graphs on $\mathrm{P}\mathrm{o}\mathrm{i}(n)$ vertices. We show that the cover time undergoes a jump at the connectivity threshold radius $r_c$: with $r_g$ denoting the threshold for having a giant component, we show that if the radius $r$ satisfies $(1+\epsilon )r_g\le r\le (1-\epsilon )r_c$ for $\epsilon >0$ arbitrarily small, the cover time of the giant component is asymptotically almost surely $\mathrm{\Theta }(n{\log }^{2}n$). On the other hand, we show that for $r\ge (1+\epsilon )r_c$, the cover time of the graph is asymptotically almost surely $\mathrm{\Theta }(n\log n)$ (which was known for $d=2$ only for a radius larger by a constant factor). Our proofs also shed some light onto the behavior around $r_c$.