Time-delayed Cops and Robbers

摘要

We consider a variation of the Cops and Robbers game in which the cops do not have perfect information; the information they receive regarding the robber’s position is delayed by one round. Our parameter of interest is the time-delayed cop number of a graph G, the minimum number of cops that suffice to guarantee a win on G. We present a variety of results on this parameter, including general bounds, and make comparisons to the cop numbers of known related variants of the original game. We have particular interest in graph products, Meyniel-type bounds, and cop density.