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 ck(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 (n/k)(1/2+o(1)) <= c(k)(n) = O(n/log (2n/k+1) log(k + 2)/k + 1), where c(k)(n) is the maximum of c(k)(G) over all n-vertex connected graphs. The parameter c(k)(G) is investigated asymptotically in random graphs G(n, p) for a wide range of p = p(n). For each k >= 0, it is shown that c(k)(G) as a function of the average degree d(n) = pn forms an intriguing zigzag shape. (C) 2010 Elsevier B.V. All rights reserved.