The cover time of a biased random walk on a random regular graph of odd degree

Abstract: We consider a random walk process which prefers to visit previously unvisited edges, on the random

r

-regular graph

G_{r}

for any odd

r g e q 3

. We show that this random walk process has asymptotic vertex and edge cover times

f r a c 1 r - 2 n l o g n

and

f r a c r 2 (r - 2) n l o g n

, respectively, generalizing the result from Cooper, Frieze and Johansson from

r = 3

to any larger odd

r

. This completes the study of the vertex cover time for fixed

r g e q 3

, with Berenbrink, Cooper and Friedetzky having previously shown that

G_{r}

has vertex cover time asymptotic to

f r a c r n 2

when

r g e q 4

is even.

This page was built for publication: The cover time of a biased random walk on a random regular graph of odd degree