Title: Cleaning regular graphs with brushes

Abstract: A model for cleaning a graph with brushes was recently
introduced. We consider the minimum number of brushes needed to clean
$d$-regular graphs in this model, focusing on the asymptotic number
for random $d$-regular graphs. We use a degree-greedy algorithm to clean a
random $d$-regular graph on $n$ vertices (with $dn$ even) and analyze
it using the differential equations method to find the (asymptotic)
number of brushes needed to clean a random $d$-regular graph using this
algorithm (for fixed $d$). We further show that for any $d$-regular
graph on $n$ vertices at most $n(d+1)/4$ brushes suffice, and prove
that for fixed large $d$, the minimum number of brushes needed to
clean a random $d$-regular graph on $n$ vertices is asymptotically
almost surely $\frac{n}{4}(d+o(d))$.

(Joint work with Noga Alon and Nick Wormald.)

http://www.mathstat.dal.ca/~pralat/papers/clean_dreg.pdf