
The game of cops and robbers, played on a fixed graph $G$, is a two-player game, where the cop and the robber (the players) take turns in moving to adjacent vertices. The game finishes if the cop lands on the robber's vertex. In that case we say that the cop wins. If the cop can always win, regardless of the starting positions, we say that $G$ is a cop-win graph. For a finite cop-win graph $G$ we can ask for the minimum number $n$ such that, regardless of the starting positions, the game will end in at most $n$ steps. This number is called the maximum capture time of $G$. By looking at finite paths, we see that any non-negative integer is the maximum capture time for a cop-win graph. What about infinite cop-win graphs? In this case, the notion of capture time is nicely generalised if one works with ordinals, and so the question becomes which ordinals can be the maximum capture time of a cop-win graph? These ordinals are called CR (Cop-Robber)-ordinals. In this paper we fully settle this by showing that all ordinals are CR-ordinals, answering a question of Bonato, Gordinowicz and Hahn.
8 pages
Combinatorics, Logic, 49N75, 91A24, 05C63, FOS: Mathematics, Combinatorics (math.CO), Logic (math.LO)
Combinatorics, Logic, 49N75, 91A24, 05C63, FOS: Mathematics, Combinatorics (math.CO), Logic (math.LO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
