Primal-Dual Cops and Robber

Authors

• Minh Tuan Ha Karlsruhe Institute of Technology
• Paul Jungeblut Karlsruhe Institute of Technology
• Torsten Ueckerdt Karlsruhe Institute of Technology
• Paweł Żyliński University of Gdańsk

Abstract

Cops and Robber is a family of two-player games played on graphs in which one player controls a number of cops and the other player controls a robber. In alternating turns, each player moves (all) their figures. The cops try to capture the robber while the latter tries to flee indefinitely. In this paper we consider a variant of the game played on a planar graph where the robber moves between adjacent vertices while the cops move between adjacent faces. The cops capture the robber if they occupy all incident faces. We prove that a constant number of cops suffices to capture the robber on any planar graph of maximum degree Δ if and only if Δ ≤ 4.

2024-01-09

How to Cite

Ha, M. T., Jungeblut, P., Ueckerdt, T., & Żyliński, P. (2024). Primal-Dual Cops and Robber. Computing in Geometry and Topology, 3(2), 4:1–4:12. https://doi.org/10.57717/cgt.v3i2.49

Section

Original Research Articles