Originators: Richard Nowakowski and Peter Winkler (presented by Bill Kinnersley - REGS 2007)
Definitions: A game is played on a graph G by k cops and l robbers. At the beginning, each cop chooses a starting vertex; subsequently, each robber chooses a starting vertex. On each turn, each player either stays in place or moves to an adjacent vertex; cops move first, then robbers. Multiple players may occupy the same vertex, and every player knows the locations of all other players at all times. If at some point every robber shares a vertex with a cop, the robbers are "caught" and the cops win the game. If the robbers can avoid capture indefinitely, then the robbers win. We say that G is a (k,l)-cop-win graph if k cops can catch l robbers on G.
Clearly |V(G)| cops can catch any number of robbers on G. Let cl(G) be the minimum number of cops that win against l robbers on G. The value c1(G) is called the cop number of G.
Background: The cop number has been fairly well studied (see below). In contrast, almost nothing is known about cl(G) for l > 1. A simple strategy shows that cl(G) ≤ c1(G)+l-1: all cops focus on one robber at a time; once he has been caught, one cop follows him for the rest of the game, and the remaining cops apply the induction hypothesis for l-1 robbers. Equality does not always hold. For example, c1(K2,n)=2, but two cops also suffice to catch two robbers.
The cop number was also described in REGS in 2005. The "polynomial time" algorithm in [BI] for determining if the cop number is at most k has running time exponential in k (but polynomial in |V(G)| as long as k is fixed). They also show that every graph is "topologically equivalent" to a graph with cop number at most 2.
A number of other references and results on cop number can be found in the survey by Alspach [Al]. Aigner and Fromme [AF] proved that three cops always suffice on a planar graph. Quilliot [Q2] generalized this, proving that c1(G) ≤ 3+2γ(G), where γ(G) is the genus of G. Andreae [An] took a different direction, proving that for all H, the cop number is bounded on the family of graphs that do not have H as a minor. He also bounded c1(G) in terms of the crosscap number. [NN] studies the behavior of cop number under various graph product operations.
Question 1: Is there a graph G such that c1(G)=c2(G)=k for some k > 2? If so, for which k is there such a graph?
Question 2: Is there a graph G such that c1(G)=c2(G) and diam(G) > 3?
Comments: It seems easy for the robbers to thwart the cops by staying far apart, thereby forcing the cops to split up. All known G for which c1(G)=c2(G) have diameter 2 or 3; in these graphs, the cops win after only one or two turns, and not much strategy is involved.
Problem 3: Characterize graphs G such that c2(G) = 2.
References:
[Al] Alspach, Brian;
Searching and sweeping graphs: a brief survey.
Matematiche (Catania) 59 (2004), no. 1-2, 5--37 (2006).
[An] Andreae, Thomas;
On a pursuit game played on graphs for which a minor is excluded.
J. Combin. Theory Ser. B 41 (1986), no. 1, 37--47.
[AF] M. Aigner; M. Fromme;
A game of cops and robbers,
Discrete Appl. Math. 8 (1984), 1--12.
[BI] Berarducci, Alessandro; Intrigila, Benedetto;
On the cop number of a graph.
Adv. in Appl. Math. 14 (1993), no. 4, 389--403.
[FN] Fitzpatrick, Shannon L.; Nowakowski, Richard J.;
Copnumber of graphs with strong isometric dimension two.
Ars Combin. 59 (2001), 65--73.
[HM] G. Hahn; G. MacGillivray;
A note on k-cop, l-robber games on graphs.
Discrete Math. 306 (2006), 2492--2497.
[NN] Neufeld, S.; Nowakowski, R.;
A game of cops and robbers played on products of graphs.
Discrete Math. 186 (1998), no. 1-3, 253--268.
[NW] R. J. Nowakowski; P. Winkler;
Vertex to vertex pursuit in a graph,
Discrete Math. 43 (1983), 235--239.
[Q1] Quilliot, A.;
Thesis, Université de Paris VI, 1983.
[Q2] Quilliot, A.
A short note about pursuit games played on a graph with a given genus.
J. Combin. Theory Ser. B 38 (1985), no. 1, 89--92.