A Note on Some Weaker Notions of Cop-Win and Robber-Win Graphs

Shravan Luckraz, Gafurjan Ibragimov and Bruno Antonio Pansera ()
Additional contact information
Gafurjan Ibragimov: Department of Digital Economics and Agrotechnologies, University of Digital Economics and Agrotechnologies, Tashkent 100022, Uzbekistan
Bruno Antonio Pansera: Department of Law, Economics and Human Sciences & Decisions Lab, University Mediterranea of Reggio Calabria, Via dell’Universitá 25, I-89124 Reggio Calabria, Italy

Mathematics, 2022, vol. 10, issue 22, 1-6

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.

Keywords: pursuit–evasion games; cop-win; robber-win; graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/22/4367/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/22/4367/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:22:p:4367-:d:978460

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().