\input zb-basic
\input zb-ioport
\iteman{io-port 05999825}
\itemau{Messinger, Margaret-Ellen; Nowakowski, Richard J.; Pra{\l}at, Pawe{\l}}
\itemti{Cleaning with brooms.}
\itemso{Graphs Comb. 27, No. 2, 251-267 (2011).}
\itemab
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 {\it N. Alon}, {\it P. Praat}, and {\it 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) \le |E|$ or $B(G) \le \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) \le B(G+e) \le 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.
\itemrv{Haiko M\"uller (Leeds)}
\itemcc{}
\itemut{graph cleaning; graph searching; chip-firing game; broom number; brush number}
\itemli{doi:10.1007/s00373-010-0965-2}
\end