# Finding a princess in a palace: A pursuit-evasion problem

- Published in 2012
- Added on

In the collections

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.

## Links

## Other information

- key
- FindingaprincessinapalaceApursuitevasionproblem
- type
- article
- date_added
- 2019-10-08
- date_published
- 2012-07-11

### BibTeX entry

@article{FindingaprincessinapalaceApursuitevasionproblem, key = {FindingaprincessinapalaceApursuitevasionproblem}, type = {article}, title = {Finding a princess in a palace: A pursuit-evasion problem}, author = {John R. Britnell and Mark Wildon}, abstract = {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.}, comment = {}, date_added = {2019-10-08}, date_published = {2012-07-11}, urls = {http://arxiv.org/abs/1204.5490v1,http://arxiv.org/pdf/1204.5490v1}, collections = {Combinatorics,Easily explained,Protocols and strategies,Puzzles}, url = {http://arxiv.org/abs/1204.5490v1 http://arxiv.org/pdf/1204.5490v1}, year = 2012, urldate = {2019-10-08}, archivePrefix = {arXiv}, eprint = {1204.5490}, primaryClass = {math.CO} }