On a pursuit-evasion model without instantaneous movement

Abstract

There is a large body of literature devoted to the graph-theoretic modeling of searching in networks. Using such terms as cops, robbers, watchmen, searchers, and intruders, these works posit the movements of pursuers and evaders from one vertex to another in a graph G, not necessarily along edges, with the respective purposes of capturing the evaders and escaping the pursuers. Various assumptions on the mobility and knowledge of the pursuers and evaders, as well as various definitions of capture, determine the graph-theoretic parameter of primary interest: the minimum number of pursuers needed to guarantee the capture of all evaders regardless of the routes elected by the evaders for escape. In this paper, we analyze a model under which pursuers and evaders move simultaneously from one vertex to another along the edges of G, none of whom moves with infinite speed. Capture of an evader occurs if and only if the evader and a pursuer are within distance one. Denoting the indicated minimum number of pursuers under our model by w(G), we determine conditions under which w(G) is at least w(H) for H a subgraph of G. We consider the relationship between w(G) and various invariants of G such as girth and diameter. And we determine w(G) for G in various classes. © 2016, University of Queensland. All rights reserved.