How to Hunt an Invisible Rabbit on a Graph

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

We investigate Hunters & Rabbit game, where a set of hunters tries to catch an invisible rabbit that slides along the edges of a graph. We show that the minimum number of hunters required to win on an (n\times m)-grid is \lfloor min{n,m}/2\rfloor+1. We also show that the extremal value of this number on n-vertex trees is between \Omega(log n/log log n) and O(log n).

Links

• http://arxiv.org/abs/1502.05614v2
• http://arxiv.org/pdf/1502.05614v2

Other information

BibTeX entry

@article{HowtoHuntanInvisibleRabbitonaGraph,
	key = {HowtoHuntanInvisibleRabbitonaGraph},
	type = {article},
	title = {How to Hunt an Invisible Rabbit on a Graph},
	author = {Tatjana V. Abramovskaya and Fedor V. Fomin and Petr A. Golovach and Micha{\l} Pilipczuk},
	abstract = {We investigate Hunters {\&} Rabbit game, where a set of hunters tries to catch
an invisible rabbit that slides along the edges of a graph. We show that the
minimum number of hunters required to win on an (n\times m)-grid is \lfloor
min{\{}n,m{\}}/2\rfloor+1. We also show that the extremal value of this number on
n-vertex trees is between \Omega(log n/log log n) and O(log n).},
	comment = {},
	date_added = {2019-10-08},
	date_published = {2015-12-07},
	urls = {http://arxiv.org/abs/1502.05614v2,http://arxiv.org/pdf/1502.05614v2},
	collections = {Animals,Attention-grabbing titles,Combinatorics,Easily explained,Protocols and strategies,Puzzles},
	url = {http://arxiv.org/abs/1502.05614v2 http://arxiv.org/pdf/1502.05614v2},
	year = 2015,
	urldate = {2019-10-08},
	archivePrefix = {arXiv},
	eprint = {1502.05614},
	primaryClass = {math.CO}
}