An Introduction to Lazy Cops and Robbers on Graphs

NEW

Problem: Reconstructed conjecture: for every $n\ge 0$,

where $Q_n$ is the $n$-dimensional hypercube with vertex set $\{0,1\}^n$, $c(G)$ is the usual cop number, and $c_L(G)$ is the lazy cop number, meaning that on each cops’ turn at most one cop may move while the others stay. This is the natural formalization of the quoted statement.

Result: The conjecture is true.

More generally, suppose $H$ is a retract of $G$ in the following cops-and-robbers sense: there is a map

such that $\rho|_{V(H)}=\mathrm{id}$, and whenever $x=y$ or $xy\in E(G)$, then $\rho(x)=\rho(y)$ or $\rho(x)\rho(y)\in E(H)$. Then

Indeed, take a winning $k$-cop strategy on $G$. In the game on $H$, place the cops at the images under $\rho$ of the starting positions prescribed in $G$. When the robber moves in $H$, regard the same move as a legal move in $G$, let the $G$-strategy respond, and project every cop position back using $\rho$. Projected cop moves are legal because $\rho$ sends closed-neighborhood moves to closed-neighborhood moves. In the lazy case, since at most one simulated cop moves in $G$, at most one projected cop moves in $H$. If the simulated strategy captures the robber at some vertex $r\in H$, then some simulated cop is also at $r$, hence its projection is $r$, so the projected strategy captures the robber in $H$. Thus both inequalities hold.

Now identify $Q_n$ with the induced subgraph of $Q_{n+1}$ consisting of vertices whose last coordinate is $0$. Define

This is a retract in the above sense: changing one coordinate in $Q_{n+1}$ either changes one of the first $n$ coordinates, giving an edge in $Q_n$, or changes only the last coordinate, giving the same projected vertex. Therefore

for all $n\ge 0$. The degenerate case $Q_0$ is harmless, since $Q_0$ is a single vertex and the same retraction argument applies.

Verification audit: no extra hypotheses beyond the standard finite-graph cops-and-robbers rules were used; the projection preserves ordinary and lazy legality; capture projects correctly because the robber remains in the retract layer.

Citation: The ordinary exact formula $c(Q_n)=\lceil (n+1)/2\rceil$ is known from Maamoun and Meyniel, “On a game of policemen and robber,” Discrete Applied Mathematics 17 (1987), 307–309. The lazy monotonicity above follows by the self-contained retract argument.