The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree

Abstract

We consider a random walk process on graphs introduced by Orenshtein and Shinkar (2014). At any time, the random walk moves from its current position along a previously unvisited edge chosen uniformly at random, if such an edge exists. Otherwise, it walks along a previously visited edge chosen uniformly at random. For the random $r$-regular graph, with $r$ a constant odd integer, we show that this random walk process has asymptotic vertex and edge cover times $\frac{1}{r-2}n\log n$ and $\frac{r}{2(r-2)}n\log n$, respectively, generalizing a result of Cooper, Frieze and the author (2018) from $r = 3$ to any odd $r\geqslant 3$. The leading term of the asymptotic vertex cover time is now known for all fixed $r\geqslant 3$, with Berenbrink, Cooper and Friedetzky (2015) having shown that $G_r$ has vertex cover time asymptotic to $\frac{rn}{2}$ when $r\geqslant 4$ is even.