  We consider random walks on several classes of graphs and explore the likely
structure of the vacant set, i.e. the set of unvisited vertices. Let \Gamma(t)
be the subgraph induced by the vacant set of the walk at step t. We show that
for random graphs G_{n,p} (above the connectivity threshold) and for random
regular graphs G_r, r \geq 3, the graph \Gamma(t) undergoes a phase transition
in the sense of the well-known Erdos-Renyi phase transition. Thus for t \leq
(1-\epsilon)t^*, there is a unique giant component, plus components of size
O(log n), and for t \geq (1+\epsilon)t^* all components are of size O(log n).
For G_{n,p} and G_r we give the value of t^*, and the size of \Gamma(t). For
G_r, we also give the degree sequence of \Gamma(t), the size of the giant
component (if any) of \Gamma(t) and the number of tree components of \Gamma(t)
of a given size k=O(log n). We also show that for random digraphs D_{n,p} above
the strong connectivity threshold, there is a similar directed phase
transition. Thus for t\leq (1-\epsilon)t^*, there is a unique strongly
connected giant component, plus strongly connected components of size O(log n),
and for t\geq (1+\epsilon)t^* all strongly connected components are of size
O(log n).

Combinatorics;Discrete Mathematics;Data Structures and Algorithms