A witness version of the cops and robber game (Q1025953)

In the usual game of cops and robbers, played on a graph with a loop at each vertex, there are \(k>0\) cops and a single robber. To begin, each of the cops chooses a vertex and then the robber chooses a vertex. The sides move alternately, a move consisting of moving along an edge to an adjacent vertex (possibly the same one, via a loop). Both sides have perfect information, and the cops win if at some time the robber and one of the cops occupy the same vertex. A graph on which a single cop can always win is called a copwin. In this paper a variation of this game is studied in which the robber still has perfect information but the cops do not. They receive information intermittently from witnesses who report sightings of the robber. This information may come at regular intervals, every \(k\) units of time (the \(k\)-regular case), or may come sporadically. A graph on which a single cop can win with sightings every \(k\) units of time is called \(k\)-winnable. Some results are obtained for irregular information games, but the bulk of the paper is devoted to \(k\)-regular games. An example is given of a copwin graph that is not \(k\)-winnable for any \(k\), and several theorems are obtained for \(k\)-regular games. Special attention is paid to triangle-free \(k\)-winnable graphs.