The robber locating game

DOI10.1016/J.DISC.2015.07.018MaRDI QIDQ501037zbMATH OpenOpenAlexFDO

Authors John Haslegrave, Richard A. B. Johnson, Sebastian Koch

Publication date 8 October 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.3867

zbMATH Keywords

cops and robberssubdivisiongraph searching

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: We consider a game in which a cop searches for a moving robber on a graph using distance probes, studied by Carragher, Choi, Delcourt, Erickson and West, which is a slight variation on one introduced by Seager. Carragher, Choi, Delcourt, Erickson and West show that for any fixed graph $G$ there is a winning strategy for the cop on the graph $G^{1/m}$, obtained by replacing each edge of $G$ by a path of length $m$, if $m$ is sufficiently large. They conjecture that the cop does not have a winning strategy on $K_n^{1/m}$ if $m<n$; we show that in fact the cop wins if and only if $mgeqslantn/2$, for all but a few small values of $n$. They also show that the robber can avoid capture on any graph of girth 3, 4 or 5, and ask whether there is any graph of girth 6 on which the cop wins. We show that there is, but that no such graph can be bipartite; in the process we give a counterexample for their conjecture that the set of graphs on which the cop wins is closed under the operation of subdividing edges. We also give a complete answer to the question of when the cop has a winning strategy on $K_{a,b}^{1/m}$.

Recommendations

• Subdivisions in the robber locating game
• scientific article; zbMATH DE number 4064802
• Cop and robber games when the robber can hide and ride
• A game of cops and robbers
• On a game of policemen and robber
• A witness version of the cops and robber game
• Locating a robber with multiple probes
• Locating a robber on a graph
• The game of cops and eternal robbers
• scientific article; zbMATH DE number 2170338

Cites work

• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 1792626 (Why is no real title available?)
• A game of cops and robbers
• An evasion game on a graph
• Chasing robbers on random graphs: zigzag theorem
• Cops and robbers in a random graph
• Cops and robbers in graphs with large girth and Cayley graphs
• Locating a backtracking robber on a tree
• Locating a robber on a graph
• Locating a robber on a graph via distance queries
• Vertex-to-vertex pursuit in a graph

Cited in

(7)

• Locating a robber with multiple probes
• Locating a backtracking robber on a tree
• Subdivisions in the robber locating game
• Approximately locating an invisible agent in a graph with relative distance queries
• A robber locating strategy for trees
• The cat and the noisy mouse
• Locating a robber on a graph

This page was built for publication: The robber locating game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501037)