This paper solves a pursuit-evasion problem in which a prince must find a princess who is constrained to move on each day from one vertex of a finite graph to another. Unlike the related and much studied `Cops and Robbers Game', the prince has no knowledge of the position of the princess; he may, however, visit any single room he wishes on each day. We characterize the graphs for which the prince has a winning strategy, and determine, for each such graph, the minimum number of days the prince requires to guarantee to find the princess.
@article{10_37236_2296,
author = {John R Britnell and Mark Wildon},
title = {Finding a princess in a palace: a pursuit-evasion problem},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2296},
zbl = {1266.05097},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2296/}
}
TY - JOUR
AU - John R Britnell
AU - Mark Wildon
TI - Finding a princess in a palace: a pursuit-evasion problem
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2296/
DO - 10.37236/2296
ID - 10_37236_2296
ER -
%0 Journal Article
%A John R Britnell
%A Mark Wildon
%T Finding a princess in a palace: a pursuit-evasion problem
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2296/
%R 10.37236/2296
%F 10_37236_2296
John R Britnell; Mark Wildon. Finding a princess in a palace: a pursuit-evasion problem. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2296
