The Library
Subdivisions in the Robber Locating game
Tools
Tools
Tools
Haslegrave, John, Johnson, Richard and Koch, Sebastian (2016) Subdivisions in the Robber Locating game. Discrete Mathematics, 339 (11). pp. 2804-2811. doi:10.1016/j.disc.2016.05.024 ISSN 0012-365X.
|
PDF
WRAP-subdivisions-Robber-locating-Haslegrave-2016.pdf - Accepted Version - Requires a PDF viewer. Download (576Kb) | Preview |
Official URL: http://www.journals.elsevier.com/discrete-mathemat...
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 m > n. 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 n if and only if m > n/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 m > n/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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Games of strategy (Mathematics) | ||||||||
| Journal or Publication Title: | Discrete Mathematics | ||||||||
| Publisher: | Elsevier BV | ||||||||
| ISSN: | 0012-365X | ||||||||
| Official Date: | 6 November 2016 | ||||||||
| Dates: |
|
||||||||
| Volume: | 339 | ||||||||
| Number: | 11 | ||||||||
| Page Range: | pp. 2804-2811 | ||||||||
| DOI: | 10.1016/j.disc.2016.05.024 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 24 June 2016 | ||||||||
| Date of first compliant Open Access: | 15 June 2017 | ||||||||
| Funder: | Seventh Framework Programme (European Commission) (FP7), National Science Foundation (U.S.) (NSF), European Union (EU), Studienstiftung des Deutschen Volkes [German National Academic Foundation] (SDV) | ||||||||
| Grant number: | Project HIERATIC 316705 (FP7), Grant DMS 1301614, MULTIPLEX grant 317532 (NSF), EP/J500380/1 (EU) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
