The cover time of a biased random walk on a random regular graph of odd degree (Q2205123): Difference between revisions

Summary: We consider a random walk process on graphs introduced by \textit{T. Orenshtein} and \textit{I. Shinkar} [Comb. Probab. Comput. 23, No. 2, 269--289 (2014; Zbl 1286.05159)]. 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 \textit{C. Cooper}, \textit{A. Frieze} and \textit{T. Johansson} [``The cover time of a biased random walk on a random cubic graph'', Preprint, \url{arXiv:1801.00760}] 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 \textit{P. Berenbrink} et al. [Random Struct. Algorithms 46, No. 1, 36--54 (2015; Zbl 1309.05165)] having shown that \(G_r\) has vertex cover time asymptotic to \(\frac{rn}{2}\) when \(r\geqslant 4\) is even.