# How to Hunt an Invisible Rabbit on a Graph

- Published in 2015
- Added on

In the collections

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

## Other information

- key
- HowtoHuntanInvisibleRabbitonaGraph
- type
- article
- date_added
- 2019-10-08
- date_published
- 2015-10-09

### 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-10-09}, 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} }