Comparing the power of cops to zombies in pursuit-evasion games

DOI10.1016/J.DAM.2019.07.026MaRDI QIDQ2009014zbMATH OpenOpenAlexFDO

Authors David Offner, Kerry Ojakian

Publication date 27 November 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypercubecops and robberspursuit-evasion gameszombies and survivors

Mathematics Subject Classification ID

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

Abstract: We compare two kinds of pursuit-evasion games played on graphs. In Cops and Robbers, the cops can move strategically to adjacent vertices as they please, while in a new variant, called deterministic Zombies and Survivors, the zombies (the counterpart of the cops) are required to always move towards the survivor (the counterpart of the robber). The cop number of a graph is the minimum number of cops required to catch the robber on that graph; the zombie number of a graph is the minimum number of zombies required to catch the survivor on that graph. We answer two questions from the 2016 paper of Fitzpatrick, Howell, Messinger, and Pike. We show that for any $mgekge1$, there is a graph with zombie number $m$ and cop number $k$. We also show that the zombie number of the $n$-dimensional hypercube is $lceil2n/3ceil$.

Recommendations

• A deterministic version of the game of zombies and survivors on graphs
• A note on deterministic zombies
• A probabilistic version of the game of zombies and survivors on graphs
• Zombie number of the Cartesian product of graphs
• Variations of cops and robber on the hypercube

Cites work

• scientific article; zbMATH DE number 6180528 (Why is no real title available?)
• A deterministic version of the game of zombies and survivors on graphs
• A game of cops and robbers
• A probabilistic version of the game of zombies and survivors on graphs
• An existence theory for pairwise balanced designs. II: Structure of PBD- closed sets and the existence conjectures
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
• Cops and robbers on graphs based on designs
• On a game of policemen and robber
• The game of cops and robbers on graphs
• Variations of cops and robber on the hypercube
• Vertex-to-vertex pursuit in a graph

Cited in

(6)

• A deterministic version of the game of zombies and survivors on graphs
• A note on deterministic zombies
• Zombie number of the Cartesian product of graphs
• How many zombies are needed to catch the survivor on toroidal grids?
• Pursuit-evasion in graphs: zombies, lazy zombies and a survivor
• A probabilistic version of the game of zombies and survivors on graphs

This page was built for publication: Comparing the power of cops to zombies in pursuit-evasion games

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