Subdivisions in the Robber Locating Game

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. Carragher, Choi, Delcourt, Erickson and West showed that for any n-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1\mathrm{/}m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m⩾n$. They conjectured that this bound was best possible for complete graphs, but the present authors showed that in fact the cop wins on $K^{1\mathrm{/}m}$ if and only if $m \geqslant n/2$,forallbutafewsmallvaluesof$n$. In this paper we extend this result to general graphs by proving that the cop has a winning strategy on $G^{1\mathrm{/}m}$ provided $m⩾n\mathrm{/}2$ for all but a few small values of $n$; this bound is best possible. We also consider replacing the edges of $G$ with paths of varying lengths.