Primal-Dual Cops and Robber
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910292274839552 |
|---|---|
| author | Ha, Minh Tuan Jungeblut, Paul Ueckerdt, Torsten Żyliński, Paweł |
| author_facet | Ha, Minh Tuan Jungeblut, Paul Ueckerdt, Torsten Żyliński, Paweł |
| contents | 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 $Δ\leq 4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_05514 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Primal-Dual Cops and Robber Ha, Minh Tuan Jungeblut, Paul Ueckerdt, Torsten Żyliński, Paweł Combinatorics Discrete Mathematics 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 $Δ\leq 4$. |
| title | Primal-Dual Cops and Robber |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2301.05514 |