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 imes m)-grid is lfloor min{n,m}/2
floor+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).
Recommendations
Cites work
- scientific article; zbMATH DE number 3997549 (Why is no real title available?)
- A short note about pursuit games played on a graph with a given genus
- An annotated bibliography on guaranteed graph searching
- An evasion game on a graph
- Escaping offline searchers and isoperimetric theorems
- Finding a princess in a palace: a pursuit-evasion problem
- Interval graphs and searching
- Randomized Pursuit-Evasion in Graphs
- Searching and pebbling
- The game of cops and robbers on graphs
- The vertex separation and search number of a graph
- Vertex-to-vertex pursuit in a graph
Cited in
(12)- Randomized pursuit-evasion with limited visibility
- Randomized Pursuit-Evasion with Local Visibility
- On evasion games on graphs
- Hunting for foxes with sheaves
- Searching for an intruder on graphs and their subdivisions
- A cops and robber game and the meeting time of synchronous directed walks
- A competitive search game with a moving target
- Limited visibility cops and robber
- Hunting rabbits on the hypercube
- Non-adaptive and adaptive two-sided search with fast objects
- scientific article; zbMATH DE number 2086681 (Why is no real title available?)
- Randomized Pursuit-Evasion in Graphs
This page was built for publication: How to hunt an invisible rabbit on a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896060)
