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

Colin Cooper, Alan Frieze

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 Γ(t) be the subgraph induced by th…