Cleaning Random d-Regular Graphs with Brooms

摘要

A model for cleaning a graph with brushes was recently introduced. Let α = (v ₁, v ₂, . . . , v _n ) be a permutation of the vertices of G; for each vertex v _i let ${N^+(v_i)={j: v_j v_i in E {rm and} j>,i}}${N^+(v_i)={j: v_j v_i in E {rm and} j>,i}} and N-(v_i)={j: v_j v_i Î E and j < i}{N^-(v_i)={j: v_j v_i in E {rm and} j<,i}} ; finally let b_a(G)=å_i=1n max{|N+(v_i)|-|N-(v_i)|,0}{b_{alpha}(G)=sum_{i=1}^n {rm max}{|N^+(v_i)|-|N^-(v_i)|,0}}. The Broom number is given by B(G) = max _α b _α (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Ö{d ln2})/4{n(d+2sqrt{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 fracn4(d+Q(Öd)){frac{n}{4}(d+Theta(sqrt{d}))}.