Cops and Attacking Robbers with Cycle Constraints

Let $G=(V,E)$ be a triangle-free graph with $\operatorname{cc}(G)=k\geq 2$ and let $u,v\in V$ such that $N(u)\subseteq N[v]$. We let $f:V\setminus\{u\}\rightarrow V$ be the identity map $f(x)=x$ for all $x\in V\setminus\{u\}$. Note that $f$ is an injective graph homomorphism, that is if $(x,y)\in E(G-u)$, then $(f(x),f(y))\in E$. We begin by arguing that a winning cop strategy in $G$ can be modified to form a winning cop strategy in $G-u$.

Consider a game of Cops and Attacking Robbers played on $G-u$ with $k=\operatorname{cc}(G)$ cops. Let the cops playing in $G-u$ be $C_{1},\dots,C_{k}$, and identify each cop with the vertex they currently occupy and do the same with the robber $R$. We will mirror this game on $G$ by placing cop $C^{\prime}_{i}$ on vertex $f(C_{i})$ for all $i\in[k]$ and placing the robber $R^{\prime}$ on vertex $f(R)$. As $f$ is a graph homomorphism, if a cop or robber moves in $G-u$ from $x$ to $y$, then the corresponding cop or robber in $G$ can move from $f(x)$ to $f(y)$, and as $f$ is injective and $G-u$ is an induced subgraph of $G$ as long as $x,y\in V\setminus\{u\}$, then the converse is also true. For each move that the robber $R$ makes in $G-u$ from $x$ to $y$, let the robber, $R^{\prime}$, in $G$ move from $f(x)$ to $f(y)$. Then let the cops $C^{\prime}_{1},\dots,C^{\prime}_{k}$ respond in $G$ using their winning strategy. Notice that as $N(u)\subseteq N[v]$, the cops never need to move onto $u$ when playing optimally in $G$ except to capture the robber on $u$. We suppose without loss of generality that cop $C^{\prime}_{i}$ never moves to $u$ except to capture the robber on $u$. Given this, if cop $C^{\prime}_{i}$ moved from $f(x)$ to $f(y)$ let the cop $C_{i}$ move from $x$ to $y$ in $G-u$. This process is well-defined as $f$ is injective and for all $x\neq u$, $x\in V\setminus\{u\}$.

As $\operatorname{cc}(G)=k$ after finitely many moves the cops in $G$ will capture the robber $R^{\prime}$. Given $f(R)=R^{\prime}$, this implies the cops in $G-u$ have also captured the robber in $G-u$. Hence, $\operatorname{cc}(G-u)\leq\operatorname{cc}(G)$.

Now suppose that $\operatorname{cc}(G-u)=t$. By Observation 2.1 our assumption that $\gamma(G-u)\geq 2$ implies that $t\geq 2$. We proceed by a similar argument except now each cop $C_{i}$ is following their winning strategy in $G-u$ to catch the robber $R=f^{-1}(R^{\prime})$ where we extend $f^{-1}$ to include that $f^{-1}(u)=v$ and allow the robber $R^{\prime}$ to pursue their optimal strategy in $G$. As $\operatorname{cc}(G-u)=t$, after finitely many moves the cops in $G-u$ will catch the robber $R=f^{-1}(R^{\prime})$. Then the cops have captured the robber in $G$ unless $R^{\prime}=u$. Suppose $R^{\prime}=u$. As the cops in $G-u$ have captured the robber $R=f^{-1}(R^{\prime})=f^{-1}(u)=v$, there is a cop $C_{i}=v$ in $G-u$, implying that there is a cop $C^{\prime}_{i}=v$ in $G$.

Since $G$ is triangle-free and $N(u)\subseteq N[v]$, observe that $v\in N(u)$ if and only if $\deg(u)=1$. At this point we assume the cops have just captured the robber in $G-u$ so it is the robber’s turn. If $\deg(u)=1$ we proceed as follows. On the previous turn in $G$, cop $C^{\prime}_{i}$ is in $N[v]$ and $R^{\prime}=u$. If there is another cop $C^{\prime}_{j}$ adjacent to a vertex $z\in N[v]$, then $C^{\prime}_{i}$ moves to $v$ and $C^{\prime}_{j}$ moves to $z$: the cops will win during their next turn. Otherwise, $C^{\prime}_{i}$ moves to a vertex in $N(v)\backslash\{u\}$ and waits for a backup cop to arrive (capturing the robber in the interim if the robber moves to $v$). As $t\geq 2$ and $G$ is connected, after finitely many turns, there will be a cop $C^{\prime}_{j}$ at $v$. At this point proceed as before. Given $v$ is the unique neighbour of $u$ during this time the robber must remain at $u$ or be immediately captured. Thus, the cops win if $\deg(u)=1$.

If $\deg(u)\neq 1$, then $v\notin N(u)$. In this case recall that $C^{\prime}_{i}=v$. Then $C^{\prime}_{i}$ waits at $v$ until a backup cop $C^{\prime}_{j}$ arrives at a vertex $N(u)$ after finitely many turns. If the robber attacks $C^{\prime}_{j}$ they will be captured by $C^{\prime}_{i}$. If the robber moves elsewhere they will be captured by $C^{\prime}_{i}$. If the robber does not move, they will be captured by $C^{\prime}_{j}$. Thus, the cops win if $\deg(u)\neq 1$.

Thus, if $\gamma(G-u)\geq 2$, then $\operatorname{cc}(G-u)\geq\operatorname{cc}(G)$. Therefore, $\operatorname{cc}(G)=\operatorname{cc}(G-u)$ as required. ∎

Let $G=(V,E)$ be a triangle-free graph that contains no dominated vertices and for which $\gamma(G)\geq 3$. Observe that the latter condition implies $\operatorname{cc}(G)\geq 2$ by Observation 2.1. For a contradiction, assume $\operatorname{cc}(G)=2$.

Suppose the cops initially occupy $u,v\in V$ (not necessarily distinct). Since $\gamma(G)\geq 3$, there is a vertex $z\in V$ such that $z\not\in N[u]\cup N[v]$. The robber $R$ initially occupies such a vertex $z$ to avoid immediate capture. As $\operatorname{cc}(G)=2$, there is a winning strategy for the cops where, for some round $t>0$, the robber occupies vertex $y$ at the beginning of round $t-1$ and regardless of the move made by the robber during round $t-1$, a cop will capture the robber during round $t$. Since $R$ could pass during round $t-1$, after the cops move during round $t-1$, there must be a cop on a neighbour $x$ of $y$; this cop moves to $y$ and captures $R$ during round $t$ if the robber passes. Thus, after the cops move during round $t-1$, a cop, say $C_{1}$, must occupy $x\in N(y)$. Observe that $R$ could move to $x$ and attack $C_{1}$ during round $t-1$. Since the robber is captured during round $t$, cop $C_{2}$ must occupy some vertex $w\in N[x]\backslash\{y\}$. Notice that any degree $1$ vertex is dominated, so we can suppose $\deg(y)>1$.

As $\deg(y)>1$, $R$ may move to $s\in N(y)\setminus\{x\}$ during round $t-1$. Since $G$ is triangle-free, $s$ is not adjacent to $x$: in this case $C_{1}$ cannot capture $R$ during round $t$. However, as $R$ is captured during round $t$, $w$ must be adjacent to every vertex in $N(y)\setminus\{x\}$ to enable $C_{2}$ to capture $R$ during round $t$. Given $x\in N(w)$ there exists a $w\neq y$ such that $N(y)\subseteq N(w)$. Since $N(w)\subset N[w]$ this implies that $N(y)\subseteq N[w]$ and hence $y$ is a dominated vertex, which is a contradiction. Thus, $\operatorname{cc}(G)>2$ as desired. ∎

Let $G=(V,E)$ be a triangle-free graph for which $\operatorname{cc}(G)\leq 2$. If $\operatorname{cc}(G)=1$, then Observation 2.1 implies $\gamma(G)=1$. Suppose $\operatorname{cc}(G)\neq 1$ for the remainder of the proof.

We begin by showing that if $\operatorname{cc}(G)\leq 2$, then $\gamma(G)\leq 2$ or for some $k\in\{1,\dots,n\}$, there is a $k$-partial domination elimination ordering $S_{k}$ of $G$ for which $\gamma(G-S_{k})\leq 2$.

Suppose that $\operatorname{cc}(G)=2$. Let $G_{0}=G$. If $G$ contains at least one dominated vertex, then form the sequence of vertices $v_{1},v_{2},\dots,v_{k}$ inductively, by considering $G_{i-1}=G-\{v_{1},\dots,v_{i-1}\}$ and letting $v_{i}$ be a fixed but arbitrary dominated vertex in $G_{i-1}$ whenever such a vertex exists. For $k\geq 1$, let $v_{1},\dots,v_{k}$ be any such sequence that is maximal, that is $G_{k}=G-\{v_{1},\dots,v_{k}\}$ has no dominated vertices. If $G$ contains no dominated vertex, set $k=0$. If $\gamma(G_{k})\leq 2$, then we have proven our result.

Suppose that $\gamma(G_{k})\geq 3$. Since $G$ is triangle-free, $G_{k}$ is also triangle-free. We may assume that $\gamma(G_{i})\geq 3$ for all $1\leq i\leq j$ because if $\gamma(G_{j})\leq 2$ for some $j<k$, then $(v_{1},v_{2},\dots,v_{j})$ would be the desired $j$-partial domination elimination ordering. Then Lemma 2.2 implies $\operatorname{cc}(G)=\operatorname{cc}(G_{1})=\dots=\operatorname{cc}(G_{k})=2$. Hence, $G_{k}$ is a triangle-free graph that contains no dominated vertices and for which $\gamma(G_{k})\geq 3$. Thus, Lemma 2.3 implies that $\operatorname{cc}(G_{k})>2$, contradicting $\operatorname{cc}(G_{k})=2$. Hence, $\gamma(G_{k})\leq 2$ as required.

For the other direction, we will prove that if $\gamma(G)\leq 2$ or for some $k\in\{1,\dots,n\}$, there is a $k$-partial domination elimination ordering $S_{k}$ of $G$ for which $\gamma(G-S_{k})\leq 2$, then $\operatorname{cc}(G)\leq 2$. Suppose that $\gamma(G)\leq 2$ or for some $k\in\{1,\dots,n\}$, there is a $k$-partial domination elimination ordering $S_{k}$ of $G$ for which $\gamma(G-S_{k})\leq 2$.

If $\gamma(G)\leq 2$, then $\operatorname{cc}(G)\leq 2$ by Observation 1.1. Suppose $\gamma(G)\geq 3$. Then for some $k\in\{1,\dots,n\}$ there is a $k$-partial domination elimination ordering $S_{k}=(v_{1},v_{2},\dots,v_{k})$ of $G$ and $\gamma(G-S_{k})\leq 2$. Observation 1.1 implies that $\operatorname{cc}(G-S_{k})\leq 2.$ Note that Observation 2.1 implies that if $\operatorname{cc}(G-S_{i})=2$, then $\gamma(G-S_{j})\geq 2$ for all $1\leq j\leq i$. So we conclude that if $\operatorname{cc}(G-S_{i})=2$ for some $i\in\{1,2,\dots,k\}$ then Lemma 2.2 implies $\operatorname{cc}(G)=\operatorname{cc}(G-S_{1})=\dots=\operatorname{cc}(G-S_{i})=2$. Hence, if $\operatorname{cc}(G-S_{k})=2$, then $\operatorname{cc}(G)=2$.

Otherwise, $\operatorname{cc}(G-S_{k})=1$. This implies $\gamma(G-S_{k})=1$ by Observation 2.1. Then either for all $i\in\{1,\dots,k\}$, $\operatorname{cc}(G-S_{i})=1$ or there exists a $1\leq j<k$ such that $j$ is the largest integer where $\operatorname{cc}(G-S_{j})>1$. If for all $i\in\{1,\dots,k\}$, $\operatorname{cc}(G-S_{i})=1$, then $\operatorname{cc}(G-v_{1})=1$. This implies $G-v_{1}$ has a universal vertex, which contradicts the assumption that $\gamma(G)\geq 3$. So there must be a largest integer $1\leq j<k$, such that $\operatorname{cc}(G-S_{j})>1$.

Letting $j$ be such an integer we claim that $\operatorname{cc}(G-S_{j})=2$. As $j<k$, there exists an integer $j+1\leq k$ and $\operatorname{cc}(G-S_{j+1})=1$. Then Observation 2.1 tells us that $\gamma(G-S_{j+1})=1$. So there exists a universal vertex $u$ in $G-S_{j+1}$. Hence, $\{u,v_{j+1}\}$ is a dominating set in $G-S_{j}$, which implies that $\gamma(G-S_{j})\leq 2$, implying the desired result that $1<\operatorname{cc}(G-S_{j})\leq 2$ by Observation 1.1 and Observation 2.1. So $\operatorname{cc}(G-S_{j})=2$. From here Lemma 2.2 implies that $\operatorname{cc}(G)=\operatorname{cc}(G-S_{j})=2$. This proves the desired result.

Therefore, $G$ has $\operatorname{cc}(G)\leq 2$ if and only if $\gamma(G)\leq 2$ or for some $k\in\{1,\dots,n\}$, there is a $k$-partial domination elimination ordering $S_{k}$ of $G$ for which $\gamma(G-S_{k})\leq 2$. This completes the proof. ∎

For the reverse implication, since $G$ does not have a universal vertex, $\operatorname{cc}(G)\geq 2$. Let $G=(V,E)$ be an outerplanar graph with no universal vertex, and at most one internal $k$-face of $\Pi$ where $k\in\{5,6\}$, and no internal $t$-face of $\Pi$ where $t>6$. We show that given the structure of $G$, two cops suffice to capture the robber.

If the cops can place themselves on a dominating set, then the robber will be captured on the first round. If this is not the case, cops $C_{1}$ and $C_{2}$ start the game by dominating the $k$-face, where $k\in\{5,6\}$, if such a face exists. The robber can then place themselves at least distance two away from cops, and survive the first round. This initial placement of the cops ensures that the robber cannot enter the $k$-face, and the cops can move in such a way that the $k$-face is always part of the cop territory, as $G$ is outerplanar.

From the initial placement, on their turn, at least one cop must move to decrease their distance to the robber, while the other cop acts as a backup cop. As $G$ is outerplanar and $G$ without the vertices of the $k$-face is comprised only of three cycles, four cycles and/or tree-like structures, the cops can move in tandem along the facial walk of the infinite face in the outerplanar embedding, while remain backup to each other and preventing the robber from entering the cop territory. Here the cop territory is all vertices $u$ such that every path from the robber to $u$ include a vertex from the closed neighbourhood of one or both cops. The cops clear the faces, one at a time, as they decrease their distance to the robber. If they are on two vertices of a $3$-cycle, the cop nearer the robber remains fixed, while the other cop moves towards the robber by moving to the third vertex of the $3$-cycle. If the cops on a $3$-cycle are at the same distance from the robber, then they move in tandem towards the robber. If the cops are on vertices of a $4$-cycle, they move in tandem along the $4$-cycle toward the robber. If the cops must traverse a portion of the graph involving a cut-vertex, the cop occupying the cut-vertex remains fixed, while the backup cop joins them on their vertex, then they move in tandem again toward the robber.

If no such $k$-face exists, the cops initially place themselves on adjacent vertices and move in tandem toward the robber using the same strategy as before. At each step, the cops increase their territory and get closer to the robber. As the graph is finite and the cops are moving in tandem, they are protecting against attacks and will capture the robber.

For the forward implication, suppose $G$ is an outerplanar graph with a fixed outerplanar embedding $\Pi$, no universal vertex, and suppose that $\operatorname{cc}(G)=2$. Suppose by way of contradiction at least one of the following hold:

1. (1)

   $\Pi$ contains at least two internal $k$-faces where $k\in\left\{5,6\right\}$, or

2. (2)

   there exists an internal $t$-face, where $t\geq 7$.

In both cases, we will show that two cops cannot capture the robber if the robber plays optimally.

1. (1)

   Suppose $\operatorname{cc}(G)=2$ and $\Pi$ contains at least two internal $k$-faces where $k\in\left\{5,6\right\}$. As $G$ is outerplanar, any two internal $k$-faces can share at most one edge. Hence, each face is an induced cycle and if $u$ is a vertex with neighbours on a face $f$, then $u$ has at most two neighbours on $f$, both of whom must be adjacent. This implies that the cop player cannot dominate both $k$-faces at the same time. The robber begins on the $k$-cycle which is not fully dominated, at distance at least two from both cops. If a cop enters the robber’s neighbourhood without backup, then the robber attacks the cop. As the domination number of the graph is greater than $1$, the remaining cop cannot then catch the robber. So if the cops want to force the robber to move, they must provide each other with backup. But the robber is on a cycle of length $5$ to more, so if the cops move in tandem around the face to force the robber to move, the robber can move to remain outside of their neighbourhood without leaving the cycle. This returns the game to the same state we began. This contradicts $\operatorname{cc}(G)=2$.

2. (2)

   Suppose $\operatorname{cc}(G)=2$ and there exists an internal $t$-face, where $t\geq 7$. The cop player can place the two cops anywhere on $G$. The robber player places themselves on the internal $t$-face where $t\geq 7$, at distance at least two from both cops. Similarly to the previous case, the cop player cannot dominate this face, and as an induced subgraph, this face corresponds to a cycle of length at least $7$ which has $\operatorname{cc}(G)=3$. Since $G$ is outerplanar there does not exist any vertex with more than $2$ neighbours on the $t$-face, hence the robber can remain on this face and evade capture indefinitely.

This completes the proof. ∎

Label the vertices of $G$ as $u_{1},u_{2},\dots,u_{n}$ where $n=|V(G)|$. Let $v_{i,j}$ be the vertex in $H$, created by subdividing edge $(u_{i},u_{j})$ of $G$. Note that the order of paired indices is unimportant: $v_{i,j}=v_{j,i}$. Label the remaining vertices of $H$ as $v_{1},v_{2},\dots,v_{n}$ where $v_{i}$ in $H$ corresponds to $u_{i}$ in $G$ for each $i$. We note that as the girth of $G$ is at least $5$, the girth of $H$ is at least $10$.

Assume $\operatorname{cc}(H)=k\leq\delta(G)$; otherwise, $\operatorname{cc}(H)\geq\delta(G)+1$ and the result holds. We further assume $k<\gamma(G)$; otherwise $\operatorname{cc}(H)\geq\gamma(G)>\delta(G)$ by Theorem 3.2 and the result holds. An implication of $\operatorname{cc}(H)=k\leq\delta(G)$ is that $cc(H)<cc(G)$ by Theorem 3.2.

Let $S=\{v_{1}^{*},v_{2}^{*},\dots,v_{k}^{*}\}$ be the set of vertices initially occupied by the cops in $H$ where $v_{i}^{*}$ corresponds to either a vertex in $G$ or to a subdivided edge of $G$. We will show that on $H$, the robber can avoid capture indefinitely, which will contradict the assumption that $\operatorname{cc}(H)=k<\operatorname{cc}(G)$. We next explain why the robber can avoid initially occupying a vertex in $H$ that corresponds to a subdivided edge of $G$, and also avoid being adjacent to a cop. For each vertex $v_{j}^{*}$ in $S$, there exists $v_{j}\in V(H)$ such that $v_{j}^{*}\in N_{H}[v_{j}]$. Since $k<\gamma(G)$, there is a vertex $u_{i}\in V(G)$ adjacent to no vertex in $\{u_{1},u_{2},\dots,u_{k}\}$ in $G$. In $H$, the robber initially occupies $v_{i}$. Note that $v_{i}$ is not adjacent to any vertex in $\{v_{1}^{*},v_{2}^{*},\dots,v_{k}^{*}\}$ in $H$, given $u_{i}$ is not adjacent to any vertex $\{u_{1},u_{2},\dots,u_{k}\}$ in $G$, and so the robber is not adjacent to a cop.

We refer to vertices $v_{1},v_{2},\dots,v_{n}$ in $H$ as core vertices. Observe that the robber initially occupies a core vertex of $H$. We will show that there is a robber strategy for which the following property holds throughout the game:

($\star$) once a cop moves to be adjacent to the robber, the robber can, after two turns, occupy a core vertex that is not adjacent to any cop.

As the robber occupies $v_{i}$, let $\deg_{H}(v_{i})=d$ and $N_{H}(v_{i})=\{v_{i,{m_{1}}},v_{i,{m_{2}}},\dots,v_{i,{m_{d}}}\}$ and suppose the robber remains on vertex $v_{i}$ until a cop enters $N_{H}(v_{i})$. If for all $t$, no cop enters $N_{H}(v_{i})$ after $t$ cop rounds, then the robber is never captured and the robber wins. Consequently, suppose there exists a $t$ such that a cop will enter $N_{H}(v_{i})$ after $t$ cop rounds where $t$ is the least integer satisfying this property. Without loss of generality, during round $t$ a cop $C$ occupies vertex $v_{i,{m_{1}}}$.

After the cops’ turn during round $t$, if there is no cop other than $C$ within distance two of $v_{m_{1}}$, then the robber moves to $v_{i,m_{1}}$, attacks the cop $C$ during round $t$, and moves to $v_{m_{1}}$ during round $t+1$. By assumption, no cop can be adjacent to core vertex $v_{m_{1}}$ at the end of round $t+1$ and ($\star$) holds.

Suppose that after the cops have moved during round $t$, there is a cop $C^{\prime}$ distinct from $C$ within distance two of $v_{m_{1}}$. Since $H$ has girth at least $10$, $C^{\prime}$ cannot be within distance two of any of $v_{m_{2}},v_{m_{3}},\dots,v_{m_{d}}$. Moreover, for all $r\neq s$, $\operatorname{dist}(v_{m_{r}},v_{m_{s}})\geq 6$ in $H-v_{i}$. Hence, $v_{i}$ is the unique vertex of $H$ which is within distance at most two from both $v_{m_{r}}$ and $v_{m_{s}}$ for any $r\neq s$. So any cop within distance two of $v_{m_{r}}$ is not within distance two of $v_{m_{s}}$ for any $r\neq s$, given the robber is on vertex $v_{i}$. Recall that $\operatorname{cc}(H)\leq\delta(G)$ and that there are two cops within distance two of $v_{m_{1}}$. This implies $k\leq d$ and so there must be a vertex $v_{m_{\ell}}$ (for some $\ell\in\{2,3,\dots,d\}$) such that there is no cop within distance two of $v_{m_{\ell}}$ after the cops move during round $t$. In this case, the robber moves to $v_{i,{m_{\ell}}}$ during round $t$, before moving to $v_{m_{\ell}}$ during round $t+1$, and there is no cop in $N[v_{m_{\ell}}]$ at the end of round $t+1$. In this case, ($\star$) holds.

Repeating the above arguments provides a robber strategy which ensures ($\star$) always holds, which contradicts $\operatorname{cc}(H)<\operatorname{cc}(G)$ and therefore also contradicts $\operatorname{cc}(H)\leq\delta(G)$. ∎

Let $G=(V,E)$ be a finite bipartite graph and $P=v_{0},\dots,v_{k}$ a geodesic path in $G$. Label the cops $C$ and $C^{\prime}$. For $0\leq i\leq k-1$, let $D_{i}$ denote the set of vertices distance $i$ from $v_{0}$ and let $D_{k}=\{u\in V:\operatorname{dist}(u,v_{0})\geq k\}$. We will assume the robber never moves to a vertex adjacent to a cop; otherwise, the cop will capture the robber during the next round.

Suppose, after some player has moved, the robber is in $D_{i}$ and the vertices occupied by the cop and robber are non-adjacent. We define several possible states a cop can be in;

• •

  if a cop occupies $v_{i}$, then the cop is in state ($0$);

• •

  if a cop occupies $v_{i-1}$, then the cop is in state ($-1$);

• •

  if a cop occupies $v_{i+1}$, then the cop is in state ($+1$).

Proof of Claim 1. We assume that $C$ and $C^{\prime}$ move together until they get to $v_{0}$ on $P$. After finitely many steps cops $C^{\prime}$ and $C$ can occupy $v_{0}$ and $v_{1}$, respectively, or the cops will have captured the robber.

Suppose the robber occupies vertex $x$. If $x\in\{v_{0},v_{1}\}$, then the cops have captured the robber. If $x\in D_{1}-v_{1}$, then $C$ is in state ($0$) as required. Suppose $x\in D_{i}$ for $i\geq 2$. During each round, the cops $C$ and $C^{\prime}$ will move from $v_{j-1}$ to $v_{j}$ until both the robber and $C$ occupy a vertex in $D_{j}$ for some $j\geq 2$. Since the geodesic path is finite, this situation must occur; when it does, suppose the robber occupies $x_{j}$ and observe that $C$ occupies $v_{j}$ and $C^{\prime}$ occupies $v_{j-1}$. We consider whose turn it is to move when this situation occurs:

1. (1)

   Suppose the robber has just moved to $x_{j}$. By assumption $x_{j}\notin N(v_{j})$, so $C$ is in state ($0$) if $x_{j}\neq v_{j}$. If $x_{j}=v_{j}$, then the cop $C^{\prime}$ will capture the robber on their next turn.

2. (2)

   Suppose the cops have just moved.

   1. (a)

      If the robber moves to a vertex $x_{j-1}\in D_{j-1}$, then by assumption, $x_{j-1}\notin N(v_{j-1})$ so $C^{\prime}$ is in state ($0$), or $C$ will capture the robber if $x_{j-1}=v_{j-1}$.

   2. (b)

      If the robber moves to a vertex $x_{j}^{\prime}\in D_{j}$, then by assumption, $x_{j}^{\prime}\notin N(v_{j})$, so $C$ is in state ($0$), or $C^{\prime}$ will capture the robber if $x^{\prime}_{j}=v_{j}$.

   3. (c)

      If the robber moves to a vertex $x_{j+1}\in D_{j+1}$, then the cops move to $v_{j},v_{j+1}$ and we are at the beginning of (2) again, except the indices are increased by one. Since the geodesic path is finite, (2)(c) can only occur finitely many times.

This concludes the proof of Claim 1. $\diamond$

Hence, after finitely many moves $C$ or $C^{\prime}$ can achieve state ($0$) with the help of the second cop, or the cops will capture the robber. Once a cop has reached state ($0$), the other cop is no longer needed to guard $P$. Suppose without loss of generality $C$ reaches state ($0$). We next show how, from state ($0$), $C$ can guard $P$.

Proof of Claim 2. For some $i\in[k]$, suppose that $C$ occupies $v_{i}$ and the robber occupies $x\in D_{i}$ where $v_{i}\notin N[x]$. We will provide a strategy for $C$ to guard the path $P$ for the rest of the game.

If it is the cops’ turn, then $C$ remains on its current vertex, and thus, remains in state ($0$). If it is the robber’s turn, then we consider the robber’s possible moves, from $x$ to $x^{\prime}$, in three cases: (i) $x^{\prime}\in D_{i}$, (ii) $i<k$ and $x^{\prime}\in D_{i+1}$, or (iii) $x^{\prime}\in D_{i-1}$. Since we assumed the robber never moves to a vertex adjacent to the cop, $x^{\prime}$ is not adjacent to $v_{i}$, and as $v_{i}\notin N(x)$, we conclude that $x^{\prime}\neq v_{i}$.

The remainder of the proof explains how the cop $C$ should respond in each case. Hence, if the cop is in state ($0$), then the robber cannot enter $P$ on their next move without moving adjacent to the cop $C$, thereby losing. It follows that if the robber has a strategy to enter $P$ without being captured, then this strategy will force $C$ to leave state ($0$). Thus, to show $C$ guards $P$ it is necessary and sufficient for us to show that if $C$ is forced to leave state ($0$), either $C$ can continue to guard $P$ from outside state ($0$) or $C$ can return to state ($0$).

1. (i)

   Suppose $x^{\prime}\in D_{i}$. Since $x^{\prime}\notin N(v_{i})$ and $x^{\prime}\in D_{i}$, the cop $C$ remains at $v_{i}$ and is in state ($0$).

2. (ii)

   Suppose $i<k$ and $x^{\prime}\in D_{i+1}$. If $x^{\prime}\notin N(v_{i+1})$, the cop moves to $v_{i+1}$ and is in state ($0$). So we assume the edge $(x^{\prime},v_{i+1})$ exists. After the robber’s turn, the cop remains on $v_{i}$ implying that the cop is now in state ($-1$). We need to show that the cop can return to state ($0$), or the cop can guard the path $P$ while remaining in state $(-1)$ indefinitely. Note that $(x^{\prime},v_{i})\notin E$, since $x^{\prime}$, $v_{i}$, and $v_{i+1}$ would form an odd cycle. See Figure 4 (a) for a visualization. If the robber does not move on their turn, the cop does not move, and has successfully prevented the robber from entering $P$. Suppose then that the robber moves to a new vertex on their turn. From this position, the robber can move to a vertex in $D_{i}$, $D_{i+1}$, or $D_{i+2}$; the latter only if $i+2\leq k$.

   First, if the robber moves to a vertex in $D_{i}\backslash N(v_{i})$ then the cop remains at $v_{i}$ and is in state ($0$).

   Second, if the robber moves to a vertex $x_{i+1}\in D_{i+1}\backslash(N(v_{i})\cup\{x^{\prime}\})$, then we note $(x_{i+1},v_{i+1})\notin E$; otherwise $\{x^{\prime},x_{i+1},v_{i+1}\}$ form a $3$-cycle. Thus, the cop moves to $v_{i+1}$ and is now in state ($0$).

   Third, if $i+2\leq k$, then suppose $R$ moves to $x_{i+2}\in D_{i+2}$. Observe that $x_{i+2}\neq v_{i+2}$; otherwise $\{x^{\prime},v_{i+1},v_{i+2}\}$ forms a $3$-cycle. Notably, $(v_{i+1},x_{i+2})\not\in E$; otherwise $\{v_{i+1},x^{\prime},x_{i+2}\}$ forms a $3$-cycle. This implies that if the robber moves to $x_{i+2}$, then the cop can safely move to $v_{i+1}$ and is now again in state $(-1)$, with an increased index on the vertices of $P$. Thus, this whole case analysis restarts from a higher index.

   Notice that if at this higher index the robber decreases their index on their turn, i.e move from $D_{j}$ to $D_{j-1}$, then by the cop $C$ in state ($-1$) can either capture the robber, or remain on their current vertex on their turn, thereby entering state ($0$). Note that as the cop is in state ($-1$), the robber cannot attack the cop. As returning to state ($0$) benefits the cop’s strategy to protect the path, we suppose that the robber does not allow to the cop to return to state ($0$). Hence, we can suppose it is the robber’s turn, and that the robber currently occupies a vertex $x_{l}\in D_{i+l}$ for some $t\geq 2$, while the cop is in state ($-1$). Without loss of generality suppose that the robber has not entered $P$ before the current turn. We will show that either the robber increases their index again, or the cop is able to enter state ($0$), or the robber enters $P$ and is captured by the cop.

   There are two cases to consider. First, the robber moves from $D_{i+l}$ to a vertex in $D_{i+l}$, second the robber moves from a vertex $D_{i+l}$ to a vertex in $D_{i+l+1}$. Of course for the second option to be possible, $i+l+1\leq k$.

   We being by considering the case where the robber moves from a vertex $x_{i+l}\in D_{i+l}$ to a vertex in $x^{\prime}_{i+l}\in D_{i+l}$. Without loss of generality we suppose that this is the first instance of the robber not increasing the index of the set $D_{j}$ they occupy on their turn. By this assumption we can suppose that on the previous $t$ turns, the robber occupies a vertex $x_{i+r}\in D_{i+r}$. Notice here that $x^{\prime}=x_{i+1}$.

   Recall that by assumption $(x^{\prime},v_{i+1})\in E$. Further we can suppose that $x_{i+l}\neq x^{\prime}_{i+l}$, because if the robber does not move, then the cop can pass on their turn without allowing the robber to make any progress towards entering the path $P$. Then, $x_{i+1},\dots,x_{i+l},x^{\prime}_{i+l}$ is a path of length $l+1$. Hence, if $(x^{\prime}_{i+l},v_{i+l})\in E$, then

   $$x_{i+1},\dots,x_{i+l},x^{\prime}_{i+l},v_{i+l},v_{i+l-1},\dots,v_{i+1}$$

   is a cycle of length $2t+1$. But $G$ is bipartite, so $G$ contains no odd cycle, hence, $(x^{\prime}_{i+l},v_{i+l})\not\in E$. Given $(x^{\prime}_{i+l},v_{i+l})\not\in E$, the cop $C$ can safely move from $v_{i+l-1}$ to $v_{i+l}$ on their turn, thereby entering state ($0$). We conclude that if the robber does not increase their index on every turn, then the cop can enter state ($0$) thereby guarding the path $P$. Suppose then that on every turn since moving to $x^{\prime}$, the robber has increased their index.

   Suppose then that the robber moves from a vertex $x_{i+l}\in D_{i+l}$ to a vertex in $x_{i+l+1}\in D_{i+l+1}$. We must prove two facts. First, $x_{i+l+1}\neq v_{i+l+1}$, and second that $x_{i+l+1}\not\in N(v_{i+l})$. We must show the first fact in order to ensure that the cop $C$ prevents the robber from entering $P$, and we must prove the second fact to ensure that the cop can move from $v_{i+l-1}$ to $v_{i+l}$ on their turn to remain in state ($-1$). Notice that the second fact implies the first. Hence, we will prove both facts by proving the second.

   Suppose that $x_{i+l+1}\in N(v_{i+l})$, then

   $$x_{i+1},\dots,x_{i+l},x_{i+l+1},v_{i+l},v_{i+l-1},\dots,v_{i+1}$$

   is a cycle of length $2l+1$. But as $G$ is bipartite, $G$ contains no odd cycle. Hence, $x_{i+l+1}\not\in N(v_{i+l})$. Thus, the robber cannot enter $P$ on their turn, and if the robber increases their index, the cop can respond by returning to state ($-1$). This concludes the proof of case (ii).

3. (iii)

   Similar to (ii) with state ($-1$) being replaced with state ($+1$).