Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777289 | Electronic Notes in Discrete Mathematics | 2017 | 8 Pages |
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
Nikolay Beluhov, Emil Kolev,