| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4646606 | Discrete Mathematics | 2016 | 8 Pages |
We consider a game in which a cop searches for a moving robber on a graph using distance probes, which is a slight variation on one introduced by Seager. Carraher, Choi, Delcourt, Erickson and West showed that for any nn-vertex graph GG there is a winning strategy for the cop on the graph G1/mG1/m obtained by replacing each edge of GG by a path of length mm, if m⩾nm⩾n. They conjectured that this bound was best possible for complete graphs, but the present authors showed that in fact the cop wins on Kn1/m if and only if m⩾n/2m⩾n/2, for all but a few small values of nn. In this paper we extend this result to general graphs by proving that the cop has a winning strategy on G1/mG1/m provided m⩾n/2m⩾n/2 for all but a few small values of nn; this bound is best possible. We also consider replacing the edges of GG with paths of varying lengths.
