How to hunt an invisible rabbit on a graph

DOI10.1016/J.EJC.2015.08.002zbMATH Open1327.05233DBLPjournals/ejc/AbramovskayaFGP16arXiv1502.05614OpenAlexW1855571088WikidataQ60488376 ScholiaQ60488376MaRDI QIDQ896060FDOQ896060

Authors: T. V. Abramovskaya, Fedor V. Fomin, Petr A. Golovach, Michał Pilipczuk 

Publication date: 11 December 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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).

Full work available at URL: https://arxiv.org/abs/1502.05614

Recommendations

• Hunting rabbits on the hypercube
• How to survive while visiting a graph
• Search for a moving target in a graph
• scientific article; zbMATH DE number 410202
• Exploring an unknown graph
• Totally magic graphs

zbMATH Keywords

Hunters \& Rabbit game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Searching and pebbling
• Vertex-to-vertex pursuit in a graph
• The game of cops and robbers on graphs
• Randomized Pursuit-Evasion in Graphs
• An annotated bibliography on guaranteed graph searching
• The vertex separation and search number of a graph
• Interval graphs and searching
• An evasion game on a graph
• A short note about pursuit games played on a graph with a given genus
• Title not available (Why is that?)
• Escaping offline searchers and isoperimetric theorems
• Finding a princess in a palace: a pursuit-evasion problem

Cited In (12)

• 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
• Title not available (Why is that?)
• Randomized Pursuit-Evasion in Graphs
• Randomized pursuit-evasion with limited visibility
• Randomized Pursuit-Evasion with Local Visibility

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)