Search for a moving target in a graph

In this paper we consider a searching game called k-chase. A Princess occupies a vertex of given graph G and a Suitor is trying to find her. On each turn, the Suitor examines k vertices of G looking for the Princess (and, if he finds her, the game ends). Following this, the Princess moves to an adjacent vertex of G and the turn is complete. For k=1, we give a complete characterization of graphs for which it is possible for the Suitor to find the Princess. We also find the minimum k for which the Suitor finds the Princess when G is a rectangular grid of size 2n×2n.