Randomized Persuit-Evasion in Graphs

and "Hunter". Both the players move between the vertices of an
undirected graph. Both players know the graph. But they see
each other only if they happen to meet at the same node in the graph.
Then hunter is "restricted" in the sense that it can move from one vertex to
the other only along the edges of the graph. But the rabbit is "unrestricted"
in the sense that it can jump from any vertex to any other vertex.
The game ends when the hunter "catches" ( or in other words meets )
the rabbit in some node. In this talk we will see good hunter strategies ( randomized ) which
catches the rabbit as soon as possible, as well as, good rabbit
strategies which evades the hunter as long as possible. Formally,
we derive upper bounds and matching lower bounds for the expected time
needed for the hunter to catch the rabbit on general graphs.
We will also see better bounds on special graphs.