Name
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. Carraher, 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 n 1 / m 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2016.05.024 | Discrete Mathematics |
Keywords | Field | DocType |
Graph searching,Cops and robbers,Subdivision | Graph,Discrete mathematics,Combinatorics,Vertex (graph theory),Subdivision,Mathematics | Journal |
Volume | Issue | ISSN |
339 | 11 | 0012-365X |
Citations | PageRank | References |
2 | 0.40 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Haslegrave | 1 | 29 | 5.74 |
| Richard A. B. Johnson | 2 | 7 | 0.93 |
| Sebastian Koch | 3 | 8 | 1.32 |