Author
Guggiari, H
Roberts, A
Scott, A
Last updated
2021-11-12T02:13:48.513+00:00
Abstract
A cat and mouse play a pursuit and evasion game on a connected graph $G$ with
$n$ vertices. The mouse moves to vertices $m_1,m_2,\dots$ of $G$ where $m_i$ is
in the closed neighbourhood of $m_{i-1}$ for $i\geq2$. The cat tests vertices
$c_1,c_2,\dots$ of $G$ without restriction and is told whether the distance
between $c_i$ and $m_i$ is at most the distance between $c_{i-1}$ and
$m_{i-1}$. The mouse knows the cat's strategy, but the cat does not know the
mouse's strategy. We will show that the cat can determine the position of the
mouse up to distance $O(\sqrt{n})$ within finite time and that this bound is
tight up to a constant factor. This disproves a conjecture of Dayanikli and
Rautenbach.
Symplectic ID
1069817
Download URL
http://arxiv.org/abs/1805.04386v1
Favourite
Off
Publication type
Journal Article
Publication date
11 May 2018
Please contact us with feedback and comments about this page. Created on 04 Nov 2019 - 12:14.