Component structure of the vacant set induced by a random walk on a random graph.

We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices (or vacant set). Let Γ(t) be the subgraph induced by the vacant set. We show that for random graphs Gn,p above the connectivity threshold, and for random regular graphs Gr, for constant r ≥ 3, there is a phase transition in the sense of the well-known Erdős-Renyi phase transition. Thus for t ≤ (1 − ∊)t* we have a unique giant plus components of size O(log n) and for t ≥ (1 + ∊)t* we have only components of size O(log n). In the case of Gr we describe the likely degree sequence and structure of the small (O(log n)) size components.