Locating a robber on a graph via distance queries

AbstractA cop wants to locate a robber hiding among the vertices of a graph. A round of the game consists of the robber moving to a neighbor of its current vertex (or not moving) and then the cop scanning some vertex to obtain the distance from that vertex to the robber. If the cop can at some point determine where the robber is, then the cop wins; otherwise, the robber wins. We prove that the robber wins on graphs with girth at most 5. We also improve the bounds on a problem of Seager by showing that the cop wins on a subdivision of an n-vertex graph G when each edge is subdivided into a path of length m, where m is the minimum of n and a quantity related to the “metric dimension” of G. We obtain smaller thresholds for complete bipartite graphs and grids