Let $G=(V,E)$ be a graph and consider a random walk on it. Let $G'=(V',E')$ be a subgraph consisting of the vertices and edges that are visited by the random walk.
Question 0: Is there a standard name for $G'$?
Intuitively $G'$ is a thin subgraph, so for instance, even when $G$ is transient, $G'$ can be recurrent.
Question 1: Is there a counterexample? So, Is there a transient graph $G$ so that $G'$ is transient with positive probability?
I'm also curious to know what happens when one iterates this procedure, $G,G',G'',\dots$. Does it eventually look like a path graph?
Question 2: What can one say about $G^{(n)}$ as $n\to \infty$?
Best Answer
Question 0: $G'$ is known as the trace of the random walk.
Question 1: $G'$ is always recurrent with probability one. This is a result of Benjamini, Gurel-Gurevich, and Lyons from 2007.
Question 2: Since $G'$ is recurrent, with probability one we have $G^{(n)}=G'$ for all $n \geq 1$.