Return to Question

• On her turn, Alice chooses a (possibly empty) subset of the cops and moves them to some adjacent vertices.

• On his turn, Bob may either move his robber to an adjacent vertex or stand still.

• The game ends with a win for Alice whenever any of her cops manages to occupy the same vertex as the robber. Bob wins if this never happens in the game.

• On her turn, Alice chooses a (possibly empty) subset of the cops and moves them to some adjacent vertices.

• On his turn, Bob may either move his robber to an adjacent vertex or stay still.

• The game ends with a win for Alice whenever any of her cops manages to occupy the same vertex as the robber. Bob wins if this never happens in the game.

Cops & Robbers is a certain pursuit-evasion game between two players, Alice and Bob. Alice is in charge of the Justice Bureau, which controls one or more law enforcement officers, the cops. Bob controls a single robber, a guy whose main concern is to evade the cops at any costs. Both deploy their guys on the vertices of a city, a simple graph, and start a manhunt under some natural rules.

Cops & Robbers is a certain pursuit-evasion game between two players, Alice and Bob. Alice is in charge of the Justice Bureau, which controls one or more law enforcement officers, the cops. Bob controls a single robber, a guy whose main concern is to evade the cops at any costs. Both deploy their guys on the vertices of a city, a simple graph, and start a manhunt under the following natural rules:

• On her turn, Alice chooses a (possibly empty) subset of the cops and moves them to some adjacent vertices.

• On his turn, Bob may either move his robber to an adjacent vertex or stand still.

• The game ends with a win for Alice whenever any of her cops manages to occupy the same vertex as the robber. Bob wins if this never happens in the game.

Remark 2. Concerning the question 2 in the special cases such as $\kappa=2^{\aleph_0}$, an approach could be thinking about using cardinal characteristics of the continuum in order to construct examples of connected (directed) graphs of size continuum with cop numbers strictly less than $2^{\aleph_0}$. In order to observe this, note that cop number of any graph is less than or equal to its domination number because one may catch the robber in the first move simply by deploying one cop on each vertex in a minimal dominating set of the graph. The idea is that the set-theoretic dominating number, $\mathfrak{d}$, serves as the domination number of a graph, $G$, of size $2^{\aleph_{0}}$ (don't confuse the similar terms in set theory and graph theory with each other). At the request of Monroe, let me clarify the example a little bit more:

Remark 2. Concerning the question 2 in the special cases such as $\kappa=2^{\aleph_0}$, an approach could be thinking about using cardinal characteristics of the continuum for constructing examples of connected (directed) graphs of size continuum with cop numbers strictly less than $2^{\aleph_0}$. In order to observe this, note that cop number of any graph is less than or equal to its domination number because one may catch the robber in the first move simply by deploying one cop on each vertex in a minimal dominating set of the graph. The idea is that the set-theoretic dominating number, $\mathfrak{d}$, serves as the domination number of a graph, $G$, of size $2^{\aleph_{0}}$ (don't confuse the similar terms in set theory and graph theory with each other). At the request of Monroe, let me clarify the example a little bit more: