Cleaning with brooms (Q659685)

Cleaning with brushes is a game on graphs that was introduced by the authors in [``Cleaning a network with brushes,'' Theor.\ Comput.\ Sci.\ 399, 191--205 (2008; Zbl 1187.68185)]. It is described in the review of a paper by \textit{N. Alon}, \textit{P. Praat}, and \textit{N. Wormald} [``Cleaning regular graphs with brushes,'' SIAM J.\ Discrete Math.\ 23, No.\,1, 233--250 (2008; Zbl 1187.05066)]. Cleaning with brooms refers to the same game. While the brush number \(b(G)\) is the minimum number of brushes needed to clean the graph \(G\), the broom number \(B(G)\) is the maximum number of brushes that can be used to clean \(G\). The paper gives various bounds on \(B(G)\), such as \(B(G) \leq |E|\) or \(B(G) \leq \lfloor|V|^2/4\rfloor\) for all graphs \(G=(V,E)\). The former bound is attained if and only if \(G\) is bipartite, and the latter bound is attained for complete graphs \(G\). For a graph \(G+e\), obtained from \(G\) by adding one edge, \(B(G) \leq B(G+e) \leq B(G)+1\) holds. We have \(b(G) = B(G)\) if and only if \(G\) is a disjoint union of complete graphs. Further bounds on \(B(G)\) are shown for the cartesian product of complete graphs and the strong product of cycles.