Most generalized Petersen graphs of girth 8 have cop number 4

NEW

Problem: Reconstructed statement: In the usual finite, simple-graph Cops and Robber game, determine $c(J_n)$, where the Isaacs flower snark $J_n$ has $n$ odd, $n\ge 5$, vertices

and edges

for all $i\in\mathbb Z_n$. The word “snark” supports the standard restriction $n$ odd and $n\ge5$.

Result:

First, $c(J_n)\ge3$. The graph is cubic and has girth at least $5$: no triangle can contain a center $a_i$, since there are no edges among $b_i,c_i,d_i$, and the leaf-induced graph has no triangle; similarly a $4$-cycle would require either a $4$-cycle in the leaf-induced graph or a length-$2$ leaf path between two leaves of the same layer, neither of which occurs.

Now suppose only two cops play. The robber chooses a vertex at distance at least $2$ from both cops; this is possible since two closed neighborhoods cover at most $8<4n$ vertices. If after a robber move he is at $v$ at distance at least $2$ from both cops, then after the cops move, each cop forbids at most one neighbor of $v$: otherwise two distinct neighbors of $v$ would both lie in one cop’s closed neighborhood, creating a triangle or $4$-cycle. Since $v$ has three neighbors, one neighbor remains safe. The robber moves there and preserves distance at least $2$. Thus two cops cannot win.

Now $c(J_n)\le3$. Let $L_i=\{a_i,b_i,c_i,d_i\}$ and $F_i=\{b_i,c_i,d_i\}$. Put one cop at $a_0$ permanently and the other two initially at $a_{n-1}$. For $1\le j\le n-1$, let

Maintain the invariant: the fixed cop is at $a_0$, the two moving cops are at $a_j$, and, unless already capturable, the robber is in $I_j$.

To pass from $j$ to $j-1$, keep one cop at $a_j$ while the other moves along

The guards at $a_0$ and $a_j$ prevent the robber from crossing out of $I_j$, since every exit uses a leaf of $F_0$ or $F_j$, where he is captured on the next cop move. When the moving cop reaches $a_{j-1}$, any robber on $a_{j-1}$ is captured, and any robber on $F_{j-1}$ must move inward to avoid immediate capture. Hence, if play continues, the robber is in $I_{j-1}$. Then keep the new cop at $a_{j-1}$ and move the old guard from $a_j$ to $a_{j-1}$ along the same path. The robber still cannot cross the guarded boundary.

Repeating for $j=n-1,n-2,\dots,2$ leaves $I_1=\varnothing$, so capture has occurred. Therefore three cops suffice.

Thus $c(J_n)=3$.

Verification audit: the proof uses exactly the standard flower snark hypotheses $n$ odd, $n\ge5$; the lower bound uses only cubicity and girth at least $5$; the upper strategy is explicit and works within the stated graph.

Citation: The problem is Morris–Runte–Skelton, “Most generalized Petersen graphs of girth 8 have cop number 4,” arXiv:2009.00693, Problem 6.5. The lower-bound idea is the standard Aigner–Fromme girth argument: M. Aigner and M. Fromme, “A game of cops and robbers,” Discrete Applied Mathematics 8 (1984), 1–12.