Locating a robber with multiple probes |
| |
Authors: | John Haslegrave Richard AB Johnson Sebastian Koch |
| |
Institution: | 1. University of Warwick, Coventry, UK;2. The King’s School, Canterbury, UK;3. University of Cambridge, Cambridge, UK |
| |
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 -vertex graph there is a winning strategy for the cop on the graph obtained by replacing each edge of by a path of length , if (Carragher et al., 2012). The present authors showed that, for all but a few small values of , this bound may be improved to , which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of vertices, rather than a single vertex, at each turn. We consider the relationship between the value of required to ensure victory on the original graph with the length of subdivisions required to ensure victory with . 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 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 . |
| |
Keywords: | Graph searching Cops and robbers Subdivision Bounded-degree graph |
本文献已被 ScienceDirect 等数据库收录! |
|