2018/01/08 by Dayanikli, Dennis, Rautenbach, Dieter
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1801.02370
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(log n) 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.