  Given a discrete random walk on a finite graph $G$, the vacant set and vacant
net are, respectively, the sets of vertices and edges which remain unvisited by
the walk at a given step $t$.%These sets induce subgraphs of the underlying
graph. Let $\Gamma(t)$ be the subgraph of $G$ induced by the vacant set of the
walk at step $t$. Similarly, let $\widehat \Gamma(t)$ be the subgraph of $G$
induced by the edges of the vacant net. For random $r$-regular graphs $G_r$, it
was previously established that for a simple random walk, the graph $\Gamma(t)$
of the vacant set undergoes a phase transition in the sense of the phase
transition on Erd\H{os}-Renyi graphs $G_{n,p}$. Thus, for $r \ge 3$ there is an
explicit value $t^*=t^*(r)$ of the walk, such that for $t\leq (1-\epsilon)t^*$,
$\Gamma(t)$ has a unique giant component, plus components of size $O(\log n)$,
whereas for $t\geq (1+\epsilon)t^*$ all the components of $\Gamma(t)$ are of
size $O(\log n)$. We establish the threshold value $\widehat t$ for a phase
transition in the graph $\widehat \Gamma(t)$ of the vacant net of a simple
random walk on a random $r$-regular graph. We obtain the corresponding
threshold results for the vacant set and vacant net of two modified random
walks. These are a non-backtracking random walk, and, for $r$ even, a random
walk which chooses unvisited edges whenever available. This allows a direct
comparison of thresholds between simple and modified walks on random
$r$-regular graphs. The main findings are the following: As $r$ increases the
threshold for the vacant set converges to $n \log r$ in all three walks. For
the vacant net, the threshold converges to $rn/2 \; \log n$ for both the simple
random walk and non-backtracking random walk. When $r\ge 4$ is even, the
threshold for the vacant net of the unvisited edge process converges to $rn/2$,
which is also the vertex cover time of the process.
