Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653340 | European Journal of Combinatorics | 2016 | 15 Pages |
Abstract
We investigate Hunters & Rabbit game on graphs, where a set of hunters tries to catch an invisible rabbit that is forced to slide along an edge of a graph at every round. We show that the minimum number of hunters required to win on an (n×m)(n×m)-grid is ⌊min{n,m}2⌋+1. We also show that the extremal value of this number on nn-vertex trees is between Ω(logn/loglogn)Ω(logn/loglogn) and O(logn)O(logn).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tatjana V. Abramovskaya, Fedor V. Fomin, Petr A. Golovach, Michał Pilipczuk,