Subdivisions in the robber locating game

DOI10.1016/J.DISC.2016.05.024MaRDI QIDQ2629293zbMATH OpenOpenAlexFDO

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

Publication date 5 July 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cops and robberssubdivisiongraph searching

Mathematics Subject Classification ID

Distance in graphs (05C12) 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, 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/m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $mgeqslantn$. 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/m}$ if and only if $mgeqslantn/2$, for all but a few small values of $n$. In this paper we extend this result to general graphs by proving that the cop has a winning strategy on $G^{1/m}$ provided $mgeqslantn/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.

Recommendations

• The robber locating game
• Locating a robber with multiple probes
• Locating a robber on a graph via distance queries
• Locating a robber on a graph
• Locating a backtracking robber on a tree

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 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 1792626 (Why is no real title available?)
• A game of cops and robbers
• A sequential locating game on graphs
• 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
• The robber locating game
• Vertex-to-vertex pursuit in a graph

Cited in

(3)

• Locating a robber with multiple probes
• The robber locating game
• A robber locating strategy for trees

This page was built for publication: Subdivisions in the robber locating game

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