Another variant of cops and robber.

Question

I am considering the following variant of the cops and robber problem, apologies if this is well-known and references are welcomed.

The set up.

Let $G=(V,E)$ be a simple finite undirected graph.

A robber function on $G$ is some $R:\mathbb Z_{\ge 0}\to V$ such that $R(t)$ and $R(t+1)$ are adjacent vertices in $G$, in particular $R(t)\neq R(t+1)$ for all $t$ (there are no loops in $G$, and the robber is always "on the move").

A cop strategy on $G$ is any function $C:\mathbb Z_{\ge 0}\to V$, with no restriction whatsoever.

We say the cop strategy $C$ captures robber $R$ if there exists some $t\in \mathbb Z_{\ge 0}$ such that $C(t)=R(t)$. Denote $T(C,R)$ to be smallest such $t$ if exist, otherwise set it to $\infty$. If $T(C,R) = \infty$, then we say $R$ avoids or evades capture by $C$.

Finally, we say the graph $G$ has a sure-capture strategy if there exists a cop strategy $C$ such that for all robber function $R$, we have $T(C,R)$ finite.

Examples.

1. If $G$ is a path graph, then $G$ has a sure-capture strategy.

2. If $G$ is a claw with three branches, each branch with two edges, then $G$ has a sure-capture strategy.

Both of above can be analyzed by looking at the parity of the possible starting positions of the robber, as these are bipartite graphs. In fact,

3. If $G$ is a star-like graph with $n\ge 3$ branches, and each branch having two edges, then $G$ has a sure-capture strategy. (Here $G$ has $2n+1$ vertices.)

Sketch. Denote the center point of $G$ as $c$, and branch $i$ consists of vertices $a_i$ and $b_i$, where $a_i$ is connected to both $c$ and $b_i$. If $n$ is odd, consider the cop strategy $C$ given by $a_1,c,a_1,c,a_2,c,\ldots,a_n,a_1,c,a_1,c,a_2,c,\ldots,a_n$. The first half ensures robber is captured if robber starts at any $a_i$ position. Now if we haven't captured the robber in the first half, then the robber must started at a $b_i$ position, which after the first half now lands in an $a_i$ position, so we repeat the strategy again. We can adapt it similarly when $n$ is even.

Some questions.

1. What simple finite graph has a sure-capture strategy? [We can easily show that if $G$ has any cycle, then $G$ does not have any sure-capture strategy. Indeed, if to the contrary that cop strategy $C$ is a sure-capture strategy on $G$ with some cycle, we can use $C$ to produce a robber function $R$ that always avoid capture, as each vertex on said cycle has degree $\ge 2$.] So they must be forests.

2. Consider then $G$ to be connected. Then $G$ has a sure-capture strategy implies $G$ is a tree. Do all trees have a sure-capture strategy? I am not so sure here, for a claw with three branches, but each branch with 3 or more edges in it, is there a sure-capture strategy?

3. If $G$ has a sure-capture strategy $C$, then for all robber function $R$, $T(C,R)$ is finite. But is $T(C,R)$ bounded over all possible $R$?

---

I am aware of the pursuit-evasion variant where both cop and robber alternate turn, both with perfect information of where each other are, both may skip go, and both must move along the edge. In such case, we analyze positions called corners (a vertex $v$ whose closed neighborhood $N[v]$ are all covered by a single vertex), and look at removal/addition of these corners. Could this be adapted here as well?

Answer 1

The answer to $(2)$ is no. The claw with three branches, each with three edges, has no sure-capture strategy.

The robber should try to stay at the centre whenever possible. To deal with the initial situation, prepend a fictitious move at $t=-1$ in which the robber is at the centre (and the cop at an arbitrary other vertex).

The robber is restricted to alternating between the two partitions, so she can go to the centre at most every other round. If she can go to the centre on two consecutive opportunities, she's OK on the move in between, as there are three options and only one can be blocked. So assume that she's at the centre at $t$ and the cop will be at the centre at $t+2$, so she can't return there immediately. Find the next time $t+2k$ at which the cop isn't at the centre, or take $k=\infty$ if there's no such time.

The cop can block one branch by going to the vertex adjacent to the centre at $t+1$, and at most one other branch by going to the vertex adjacent to the centre at $t+2k-1$. That leaves at least one branch for the robber to take to move safely from and to the centre on those two moves. Since the cop is always at the centre on the “even” moves $t+2j$ with $0\lt j\lt k$, the robber can always be at the vertex at distance $2$ from the centre on these moves. If there are extra “odd” moves between these moves, she has two options at distance $1$ or $3$ from the centre, and only one of them can be blocked on each move. Thus she can return safely to the centre.