Sweeping Graphs and Digraphs

Searching a network for an intruder is an interesting and difficult problem. Sweeping is one such search model, in which we "sweep" for intruders along edges. The minimum number of sweepers needed to clear a graph G is known as the sweep number sw(G). The sweep number can be restricted by insisting the sweep be monotonic (once an edge is cleared, it must stay cleared) and connected (new clear edges must be incident with already cleared edges). We will examine several lower bounds for sweep number, among them minimum degree, clique number, chromatic number, and girth. We will make use of several of these bounds to calculate sweep numbers for several infinite families of graphs. In particular, these families will answer some open problems regarding the relationships between the monotonic sweep number, connected sweep number, and monotonic connected sweep number. While sweeping originated in simple graphs, the idea may be easily extended to directed graphs, which allow for four different sweep models. We will examine some interesting non-intuitive sweep numbers and look at relations between these models. We also look at bounds on these sweep numbers on digraphs and tournaments.