Article ID Journal Published Year Pages File Type
5777289 Electronic Notes in Discrete Mathematics 2017 8 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,