Subdivisions in the robber locating game

DOI10.1016/J.DISC.2016.05.024zbMATH Open1339.05254arXiv1509.04701OpenAlexW2951735999MaRDI QIDQ2629293FDOQ2629293

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

Publication date: 5 July 2016

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, 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.

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

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

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)

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?)
• 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
• The robber locating game
• A sequential locating game on graphs

Cited In (3)

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

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)