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

• Published in 2012
• Added on 2019-10-08

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

• http://arxiv.org/abs/1204.5490v1
• http://arxiv.org/pdf/1204.5490v1

Other information

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-11-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}
}