Second-Order Cover Time of Random Regular Graphs

Let $G_N$ be a uniform random $d$-regular graph on $N$ vertices, with $d\ge3$ fixed. Cooper and Frieze showed that the cover time of simple random walk on $G_N$ is asymptotically $θ_dN\log N$, where $θ_d=(d-1)/(d-2)$. We prove that, in probability over the graph and uniformly in the starting point,