On the jump of the cover time in random geometric graphs

Carlos Martinez, Dieter Mitsche

Published 2025-01-05Version 1

In this paper we study the cover time of the simple random walk of the giant component of supercritical $d$-dimensional random geometric graphs on $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 $r_c < r \le (1-\varepsilon)r_g$ for any $\varepsilon > 0$, the cover time of the giant component is asymptotically almost surely $\Theta(n \log^2 n$). On the other hand, we show that for $r \ge (1+\varepsilon)r_c$, the cover time of the graph is asymptotically almost surely $\Theta(n \log n)$ (which was known for $d=2$ only for a radius larger by a constant factor).