Article quick-view

Research paper by

Alan Frieze, Michael Krivelevich, Peleg Michaeli, Ron Peled

This paper is not available for free

You can find the original article on the journal website.

Go to sourceWe study graph-theoretic properties of the trace of a random walk on a random graph. We show that for any $\varepsilon>0$ there exists $C>1$ such that the trace of the simple random walk of length $(1+\varepsilon)n\ln{n}$ on the random graph $G\sim G(n,p)$ for $p>C\ln{n}/n$ is, with high probability, Hamiltonian and $\Theta(\ln{n})$-connected. In the special case $p=1$ (i.e. when $G=K_n$), we show a hitting time result according to which, with high probability, exactly one step after the last vertex has been visited, the trace becomes Hamiltonian, and one step after the last vertex has been visited for the $k$'th time, the trace becomes $2k$-connected.