Originators: Suzanne Seager (presented by Douglas West - REGS 2011)
Definitions: A robber is hiding at some vertex in a graph G. A cop wants to locate the robber. On each turn, the cop can probe a vertex, obtaining the distance in G from that vertex to the robber. After the probe, the robber can move distance at most 1 in G, but the robber is not allowed to move to the vertex just probed (perhaps it is still "hot"). The cop wins if, after some finite number of steps, the location of the robber is known. The final probe does not need to be at the vertex where the robber is, and there is no guarantee of knowing where the robber goes after having been located.
Question 1: On which graphs does the game last forever? When the cop does win in finite time, how long does it take?
Comments: Although the cop wins on K3, it seems that the robber wins on G whenever K4⊆G. For cycles, except very short ones, the cop wins in two rounds.
Seager [S] showed that the cop always wins when G is a tree. Furthermore, the number of turns needed on an n-vertex tree is at most n-2 (for n≥3), with equality only for stars. She showed that if the tree has only one vertex with degree larger than 2, then the number of turns needed is the maximum degree minus 1. Her algorithm on arbitrary trees designates a root and then ensures that if the robber ever moves to the root, then the next probe shows that the robber is at the root.
Background: An analogous game in which the cop needs to catch the robber has been well studied. There the cop also moves by distance at most 1, and both players know each others' movements. The graphs on which the cop wins are called "cop-win" graphs (characterized in [NW]). More generally, the cop number of a graph G is the minimum number of cops needed to catch the robber in that model. Many variations have been studied, including allowing the robber to move distance s on each move (see [AM]_. The game in the present problem is quite different from these. Nevertheles, the cop number motivates a corresponding parameter here.
Question 2: When the cop loses the location game, how many probes per turn would allow the cop to win? Call this the cop location number of G. What can be said about the cop location number and about the number of rounds needed to win when the needed number of probes per round is provided?
Comments: It seems clear that the cop location number of Kn is n/2 minus some small constant.
A more general game is defined by introducing a parameter k such that a probe returns the distance from the robber if that distance is at most K. For example, when k=1 a probe only says whether or not the robber is at the probed vertex. For each k, one can ask the same questions as before for any graph.
References:
[AM] Alon, Noga; Mehrabian, Abbas. On a generalization of Meyniel's conjecture
on the Cops and Robbers game. Electron. J. Combin. 18 (2011), Paper 19,
7 pp.
[NW] Nowakowski, Richard; Winkler, Peter. Vertex-to-vertex pursuit in a graph.
Discrete Math. 43 (1983), 235-239.
[S] S. Seager, lecture at CanaDAM 2011.