Cops and Robbers from a distance

Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance k Cops and Robbers, where the cops win if at least one of them is of distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written c_k(G), equals the minimum number of cops needed to win at a given distance k. We study the parameter c_k from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded c_k(G) values and develop an O(n^2s+3) algorithm for determining if c_k(G)≤s for s fixed. We prove that if s is not fixed, then computing c_k(G) is NP-hard. Upper and lower bounds are found for c_k(G) in terms of the order of G. We prove that