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

Shravan Luckraz, Gafurjan Ibragimov, Bruno Antonio Pansera

Research output: Journal PublicationArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Article number4367
Issue number22
Publication statusPublished - Nov 2022
Externally publishedYes


  • cop-win
  • graph
  • pursuit–evasion games
  • robber-win

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Mathematics (all)
  • Engineering (miscellaneous)


Dive into the research topics of 'A Note on Some Weaker Notions of Cop-Win and Robber-Win Graphs'. Together they form a unique fingerprint.

Cite this