preprint · The Electronic Journal of Combinatorics · 2020

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

Cited by 0Open access

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.

Cite this paper

APA 7

Johansson, T. (2020). The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree. The Electronic Journal of Combinatorics, 27(4). https://doi.org/10.37236/8327

MLA 9

Johansson, Tony. “The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree.” The Electronic Journal of Combinatorics, vol. 27, no. 4, 2020, https://doi.org/10.37236/8327.

Chicago

Johansson, Tony. 2020. “The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree.” The Electronic Journal of Combinatorics 27 (4). https://doi.org/10.37236/8327.

Harvard

Johansson, T. (2020) ‘The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree’, The Electronic Journal of Combinatorics, 27(4). Available at: https://doi.org/10.37236/8327.

BibTeX

@misc{johansson2020cover,
  title = {{The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree}},
  author = {Johansson, Tony},
  journal = {The Electronic Journal of Combinatorics},
  volume = {27},
  number = {4},
  year = {2020},
  doi = {10.37236/8327}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.