The Library
Locating a robber with multiple probes
Tools
Haslegrave, John, Johnson, Richard A. B. and Koch, Sebastian (2018) Locating a robber with multiple probes. Discrete Mathematics, 341 (1). pp. 184-193. doi:10.1016/j.disc.2017.08.028 ISSN 0012-365X.
|
PDF
WRAP-locating-robber-multiple-probes-Haslegrave-2017.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (690Kb) | Preview |
Official URL: https://doi.org/10.1016/j.disc.2017.08.028
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 (2012). 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 G1∕m obtained by replacing each edge of G by a path of length m, if m≥n (Carragher et al., 2012). The present authors showed that, for all but a few small values of n, this bound may be improved to m≥n∕2, which is best possible (Haslegrave et al., 2016). 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 with 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 Δ, which is best possible up to a factor of (1−o(1)).
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | Discrete Mathematics | ||||||||
Publisher: | Elsevier BV | ||||||||
ISSN: | 0012-365X | ||||||||
Official Date: | January 2018 | ||||||||
Dates: |
|
||||||||
Volume: | 341 | ||||||||
Number: | 1 | ||||||||
Page Range: | pp. 184-193 | ||||||||
DOI: | 10.1016/j.disc.2017.08.028 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 23 August 2017 | ||||||||
Date of first compliant Open Access: | 24 January 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year