3 papers
math.CO2014
A note on the vacant set of random walks on the hypercube and other regular graphs of high degree
Colin Cooper, Alan Frieze
We consider a random walk on a -regular graph where and satisfies certain conditions. Our prime example is the -dimensional hypercube, which has …
math.CO2014
Vacant sets and vacant nets: Component structures induced by a random walk
Colin Cooper, Alan Frieze
Given a discrete random walk on a finite graph , the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given st…
math.CO2010
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…