Hunting rabbits on the hypercube

DOI10.1016/J.DISC.2018.10.011MaRDI QIDQ1625793zbMATH OpenOpenAlexWikidataFDO

Authors Jessalyn Bolkema, Corbin Groothuis

Publication date 29 November 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cops and robbershypercubesisoperimetric inequalities

Mathematics Subject Classification ID

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

Abstract: We explore the Hunters and Rabbits game on the hypercube. In the process, we find the solution for all classes of graphs with an isoperimetric nesting property and find the exact hunter number of $Q^n$ to be $$. In addition, we extend results to the situation where we allow the rabbit to not move between shots.

Recommendations

• How to hunt an invisible rabbit on a graph
• Variations of cops and robber on the hypercube
• Randomized Pursuit-Evasion in Graphs
• The capture time of the hypercube
• scientific article; zbMATH DE number 2086681

Cites work

• An Isoperimetric Inequality on the Discrete Torus
• Finding a princess in a palace: a pursuit-evasion problem
• How to hunt an invisible rabbit on a graph
• scientific article; zbMATH DE number 736286 (Why is no real title available?)
• Odd and even Hamming spheres also have minimum boundary
• Optimal numberings and isoperimetric problems on graphs
• The game of cops and robbers on graphs

Cited in

(7)

• Hunting for foxes with sheaves
• A cops and robber game and the meeting time of synchronous directed walks
• Hunting a rabbit is hard
• Complexity results for a cops and robber game on directed graphs
• Further results on the hunters and rabbit game through monotonicity
• Hunting a rabbit: complexity, approximability and some characterizations
• How to hunt an invisible rabbit on a graph

This page was built for publication: Hunting rabbits on the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1625793)