Name
Abstract | ||
|---|---|---|
In a pursuit evasion game on a finite, simple, undirected, and connected graph G, a first player visits vertices m1,m2,… of G, where mi+1 is in the closed neighborhood of mi for every i, and a second player probes arbitrary vertices c1,c2,… of G, and learns whether or not the distance between ci+1 and mi+1 is at most the distance between ci and mi. Up to what distance d can the second player determine the position of the first? For trees of bounded maximum degree and grids, we show that d is bounded by a constant. We conjecture that d=O(logn) for every graph G of order n, and show that d=0 if mi+1 may differ from mi only if i is a multiple of some sufficiently large integer. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.disc.2018.05.006 | Discrete Mathematics |
Keywords | Field | DocType |
Pursuit and evasion game | Integer,Discrete mathematics,Binary logarithm,Combinatorics,Vertex (geometry),Pursuit-evasion,Degree (graph theory),Connectivity,Conjecture,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
341 | 8 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dennis Dayanikli | 1 | 0 | 0.34 |
| Dieter Rautenbach | 2 | 946 | 138.87 |