Locating a robber with multiple probes

DOI10.1016/J.DISC.2017.08.028MaRDI QIDQ2411615zbMATH OpenOpenAlexFDO

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

Publication date 24 October 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.06482, http://wrap.warwick.ac.uk/91522/7/WRAP-locating-robber-multiple-probes-Haslegrave-2017.pdf

zbMATH Keywords

bounded-degree graphcops and robbersgraph searchingsubdivision

Mathematics Subject Classification ID

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

Abstract: We consider a game in which a cop searches for a moving robber on a connected 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 $mgeqn$. The present authors showed that, for all but a few small values of $n$, this bound may be improved to $mgeqn/2$, which is best possible. In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph and the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $Delta$, which is best possible up to a factor of $(1-o(1))$.

Recommendations

• Subdivisions in the robber locating game
• The robber locating game
• Locating a robber on a graph
• Locating a robber on a graph via distance queries
• Locating a backtracking robber on a tree

Cites work

• A sequential locating game on graphs
• An evasion game on a graph
• Cop vs. gambler
• Cops and robbers in graphs with large girth and Cayley graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Finding a princess in a palace: a pursuit-evasion problem
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 3650583 (Why is no real title available?)
• 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 2006659 (Why is no real title available?)
• Locating a backtracking robber on a tree
• Locating a robber on a graph
• Locating a robber on a graph via distance queries
• Randomized Pursuit-Evasion in Graphs
• Recontamination does not help to search a graph
• Subdivisions in the robber locating game
• The complexity of searching a graph
• The robber locating game
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width
• Vertex-to-vertex pursuit in a graph

Cited in

(22)

• Localization game on geometric and planar graphs
• A note on the localization number of random graphs: diameter two case
• Localization game for random graphs
• Localization game for random geometric graphs
• The localization capture time of a graph
• The localization game on Cartesian products
• A robber locating strategy for trees
• Locating a backtracking robber on a tree
• Subdivisions in the robber locating game
• The robber locating game
• Connected Search for a Lazy Robber
• Sequential metric dimension
• Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• Connected search for a lazy robber
• scientific article; zbMATH DE number 7720720 (Why is no real title available?)
• The localization number of designs
• Centroidal localization game
• A note on robber locating game
• Runner locating with multiple probes
• The localization game on locally finite trees (extended abstract)
• Locating a robber on a graph
• Localization game capture time of trees and outerplanar graphs

This page was built for publication: Locating a robber with multiple probes

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