ABSTRACT
The graph cleaning model is a graph searching game that considers the decontamination of a graph by sending brushes from vertex to vertex. Graph cleaning may be viewed as a combination of the chip-firing game and edge searching on graphs. The assumption is that a graph is cleaned when every vertex has been cleaned. If every vertex has been cleaned, then it follows that every edge has been cleaned. This chapter introduces the Differential Equation (DE) method, that is powerful and has many applications in analyzing random processes, including random graphs. In the DE method, the expected changes are derived in a sequence of random variables in a given process over time. Concentration results then show that the solutions to the differential equations are close to the values of the (discrete) variables. The differential equation method is used to find an upper bound on the number of brushes needed to clean a random d-regular graph using a degree-greedy algorithm.
