2014/10/30 by Florian Lehner, Lehner, Florian · 1 citation
Computer Science · Decision Sciences · Mathematics · #05C57 (Primary) 91A46 #05C63 (Secondary) #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete mathematics #FOS: Mathematics #Game Theory and Applications #Graph #Mathematics #math.CO #msc:05C57 #msc:05C63 #msc:91A46
paper · pdf · doi:10.48550/arxiv.1410.8412
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2014/10/30 · arxiv created 2015/03/30 · arxiv updated 2015/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cops and robbers is a game between two players, where one tries to catch the other by moving along the edges of a graph. It is well known that on a finite graph the cop has a winning strategy if and only if the graph is constructible and that finiteness is necessary for this result. We propose the notion of weakly cop-win graphs, a winning criterion for infinite graphs which could lead to a generalisation. In fact, we generalise one half of the result, that is, we prove that every constructible graph is weakly cop-win. We also show that a similar notion studied by Chastand et al. (which they also dubbed weakly cop-win) is not sufficient to generalise the above result to infinite graphs. In the locally finite case we characterise the constructible graphs as the graphs for which the cop has a so-called protective strategy and prove that the existence of such a strategy implies constructibility even for non-locally finite graphs.