Cleaning Random d-Regular Graphs with Brooms

A model for cleaning a graph with brushes was recently introduced. Let alpha = (v(1), v(2),...,v(n)) be a permutation of the vertices of G; for each vertex v(i) let N(+)(v(i)) = {j : v(j)v(i) is an element of E and j > i} and N(-) (v(i)) = {j : v(j)v(i) is an element of E and j < i}; finally let b(alpha)(G) = Sigma(n)(i=1) max{vertical bar N+(v(i))vertical bar - vertical bar N(-)(v(i))vertical bar, 0}. The Broom number is given by B(G) = max(alpha) b(alpha)(G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound 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 (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d + 2 root d ln 2)/4 brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely n/4 (d + Theta (root d)).