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.
2022
pursuit–evasion games; cop-win; robber-win; graph
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12318/131427
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact