科研之友
微信
新浪微博
Facebook
分享链接
摘要
A model for cleaning a graph with brushes was first introduced by Messinger, Nowakowski, and Pralat in 2008. Later, they focused on the problem of determining the maximum number of brushes needed to clean a graph. This maximum number of brushes needed to clean a graph in the model is called the broom number of the graph. In this paper, we show that the broom number of a graph is equal to the size of a maximum edge-cut of the graph, and prove the NP-completeness of the problem of determining the broom number of a graph. As an application, we determine the broom number exactly for the Cartesian product of two graphs.
