The game of pursuit and evasion, when played on graphs, is often referred to as the game of cops and robbers. This classical version of the game has been completely solved by Nowakowski and Winkler, who gave the exact class of graphs for which the pursuer can win the game (cop-win). When the graph does not satisfy the dismantlability property, Nowakowski and Winkler’s Theorem does not apply. In this paper, we give some weaker notions of cop-win and robber-win graphs. In particular, we fix the number of cops to be equal to one, and we ask whether there exist sets of initial conditions for which the graph can be cop-win or robber-win. We propose some open questions related to this initial condition problem with the goal of developing both structural characterizations and algorithms that are computable in polynomial time (P) and that can solve weakly cop-win and weakly- robber-win graphs.
A Note on Some Weaker Notions of Cop-Win and Robber-Win Graphs / Luckraz, Shravan; Ibragimov, Gafurjan; Pansera, Bruno Antonio. - In: MATHEMATICS. - ISSN 2227-7390. - 10:22(2022), p. 4367. [10.3390/math10224367]
A Note on Some Weaker Notions of Cop-Win and Robber-Win Graphs
Pansera, Bruno Antonio
Formal Analysis
2022-01-01
Abstract
The game of pursuit and evasion, when played on graphs, is often referred to as the game of cops and robbers. This classical version of the game has been completely solved by Nowakowski and Winkler, who gave the exact class of graphs for which the pursuer can win the game (cop-win). When the graph does not satisfy the dismantlability property, Nowakowski and Winkler’s Theorem does not apply. In this paper, we give some weaker notions of cop-win and robber-win graphs. In particular, we fix the number of cops to be equal to one, and we ask whether there exist sets of initial conditions for which the graph can be cop-win or robber-win. We propose some open questions related to this initial condition problem with the goal of developing both structural characterizations and algorithms that are computable in polynomial time (P) and that can solve weakly cop-win and weakly- robber-win graphs.File | Dimensione | Formato | |
---|---|---|---|
mathematics-10-04367-v2.pdf
solo utenti autorizzati
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
257.14 kB
Formato
Adobe PDF
|
257.14 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.