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

DOI10.1016/J.DAM.2019.07.026zbMATH Open1428.05219arXiv1809.03049OpenAlexW2967630780MaRDI QIDQ2009014FDOQ2009014

David Offner, Kerry Ojakian

Publication date: 27 November 2019

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

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

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

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

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)

Cites Work

• On a game of policemen and robber
• Vertex-to-vertex pursuit in a graph
• Title not available (Why is that?)
• A game of cops and robbers
• Variations of cops and robber on the hypercube
• A deterministic 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
• Cops and robbers on graphs based on designs
• A probabilistic version of the game of zombies and survivors on graphs
• Title not available (Why is that?)
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures

Cited In (2)

• A note on deterministic zombies
• Zombie number of the Cartesian product of 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)