The robber locating game

DOI10.1016/J.DISC.2015.07.018zbMATH Open1322.05095arXiv1311.3867OpenAlexW2949940531MaRDI QIDQ501037FDOQ501037

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

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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}$.

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

Recommendations

• Subdivisions in the robber locating game
• scientific article
• 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

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)

Cites Work

• Cops and robbers in graphs with large girth and Cayley graphs
• Vertex-to-vertex pursuit in a graph
• Cops and robbers in a random graph
• Chasing robbers on random graphs: Zigzag theorem
• A game of cops and robbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locating a robber on a graph via distance queries
• An evasion game on a graph
• Title not available (Why is that?)
• Locating a robber on a graph
• Locating a backtracking robber on a tree

Cited In (6)

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

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)