2014/10/30 by Florian Lehner, Lehner, Florian
Computer Science · Decision Sciences · #05C57 (Primary) 91A46 #05C63 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1410.8412
openalex publication_date 2014/10/30 · 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.