Name
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)). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.disc.2017.08.028 | Discrete Mathematics |
Keywords | Field | DocType |
Graph searching,Cops and robbers,Subdivision,Bounded-degree graph | Discrete mathematics,Combinatorics,Bound graph,Graph power,Vertex (graph theory),Cycle graph,Regular graph,Degree (graph theory),Distance-regular graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
341 | 1 | 0012-365X |
Citations | PageRank | References |
1 | 0.40 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Haslegrave | 1 | 29 | 5.74 |
| Richard A. B. Johnson | 2 | 1 | 0.40 |
| Sebastian Koch | 3 | 8 | 1.32 |