betaFeedback

WorksMathematics

The cop number of the flower snarks, and the generalized Petersen graphs with cop number two

Abstract

We study two questions of Morris, Runte and Skelton (Australas. J. Combin. 83 (2022)) on the game of Cops and Robbers. First, we show that the flower snark JnJ_n has cop number 33 for every n≥5n\geq 5, and that J3J_3 has cop number 22. The upper bound comes from a three-cop strategy, which we call the rolling wall. It works on every connected graph whose vertices can be arranged in a cycle of columns, each dominated by a single vertex. Because only one cop moves on each turn, the same strategy also shows that the lazy cop number of JnJ_n is 33 for n≥5n\geq 5. Second, we prove the conjecture of Morris, Runte and Skelton that the only generalized Petersen graphs with cop number 22 are GP(n,1)\mathrm{GP}(n,1) and the four graphs GP(6,2)\mathrm{GP}(6,2), GP(8,2)\mathrm{GP}(8,2), GP(9,3)\mathrm{GP}(9,3) and GP(12,3)\mathrm{GP}(12,3). The new ingredient is an explicit robber strategy showing that two cops do not suffice on GP(3k,k)\mathrm{GP}(3k,k) and GP(4k,k)\mathrm{GP}(4k,k) for k≥4k\geq 4. The theorem on flower snarks and all of the new lower bounds have been formally verified in the Lean 4 proof assistant.

Introduction

In the game of Cops and Robbers, introduced by Nowakowski and Winkler [8], a team of cops tries to catch a robber on a finite graph. Both sides move along edges and see everything. The cop number c(G)c(G) is the least number of cops that can guarantee a capture. Aigner and Fromme [1] showed that graphs of girth at least 5 and minimum degree δ\delta have c(G)≥δc(G) \ge\delta. For background see the book of Bonato and Nowakowski [3].

The generalized Petersen graphs GP⁡(n,k)\operatorname{GP}(n,k) are cubic, and they have been a testing ground for the game. Ball, Bell, Guzman, Hanson-Colvin and Schonsheck [2] proved that c(GP⁡(n,k))≤4c(\operatorname{GP}(n,k)) \le4 for all n,kn,k. Morris, Runte and Skelton [7] showed that the bound 4 is attained by most generalized Petersen graphs of girth 8. They ended their paper with several open questions. Two of them are answered here. The first concerns another family of cubic graphs, the flower snarks of Isaacs [5].

Problem 1.1 ([7], Problem 6.6). What is the cop number of the flower snark JnJ_n?

Theorem 1.2. c(J3)=2c(J_3) = 2, and c(Jn)=3c(J_n) = 3 for every n≥5n \ge5. Moreover, the lazy cop number of JnJ_n is 3 for every n≥5n \ge5.

(Isaacs’s flower snarks are the graphs JnJ_n with nn odd, since only those are snarks. The theorem holds for every n≥5n \ge5.)

An earlier public, AI-generated exploration on ProbXiv [10] also states c(Jn)=3c(J_n) = 3 for odd n≥5n \ge5 and sketches a guarded-column strategy similar to the one below. That entry reports no human examination. Our flower-snark treatment additionally proves the lazy-cop statement and the even-nn extension, states the general cyclic-decomposition lemma, and includes formal verification. We cite the entry as a prior public claim, not as a peer-reviewed proof.

The second question is a conjecture stated in the same paper [7 p. 221]. A generalized Petersen graph is never cop-win, and it can have cop number 2 only if its girth is 3 or 4. All such graphs with n≤40n \le40 are known [2].

Conjecture 1.3 (Morris, Runte, Skelton [7]). The only generalized Petersen graphs with cop number 2 are GP⁡(n,1)\operatorname{GP}(n,1) for n≥3n \ge3 and GP⁡(3k,k)\operatorname{GP}(3k,k), GP⁡(4k,k)\operatorname{GP}(4k,k) for k∈{2,3}k \in\{2,3\}.

Theorem 1.4. Conjecture 1.3 is true. Equivalently, if k≥4k \ge4 then c(GP⁡(3k,k))≥3c(\operatorname{GP}(3k,k)) \ge3 and c(GP⁡(4k,k))≥3c(\operatorname{GP}(4k,k)) \ge3.

Methods

The lower bound c(Jn)≥3c(J_n) \ge3 follows from the Aigner–Fromme argument once one knows that JnJ_n has girth at least 5 for n≥5n \ge5. The upper bound is the substance of Theorem 1.2. In JnJ_n, the vertex aia_i is adjacent to bi,ci,dib_i,c_i,d_i, so it dominates the “column” {ai,bi,ci,di}\{a_i,b_i,c_i,d_i\}, and every edge joins two equal or consecutive columns. A cop on aia_i is therefore a wall the robber cannot cross. Two such walls confine the robber, and a third cop moves the walls closer together (Lemma 3.5).

For Theorem 1.4 the girth-3 and girth-4 cases are GP⁡(3k,k)\operatorname{GP}(3k,k) and GP⁡(4k,k)\operatorname{GP}(4k,k). There the Aigner–Fromme argument fails, and we replace it by an explicit set of safe positions for the robber, which he can stay inside forever (§ 4).

Verification

  • The statement “c(Jn)=3c(J_n)=3 for all n≥5n \ge5” has been formally verified in Lean 4 with Mathlib [4, 11], for every nn, without computer search (§ 6).

  • So has the statement “c(GP⁡(n,k))≥3c(\operatorname{GP}(n,k)) \ge3 unless k=1k=1 or (n,k)(n,k) is one of the four listed pairs”.

  • All the results were also checked by exhaustive computation for small parameters, using two independent solvers (§ 5).

Preliminaries

All graphs are finite and simple. N(x)N(x) is the neighbourhood of xx and N[x]=N(x)∪{x}N[x]=N(x)\cup\{x\} is the closed neighbourhood. We say that xx dominates yy if y∈N[x]y \in N[x].

The game

A game with kk cops on a graph GG goes as follows.

  1. The cops choose kk vertices (not necessarily distinct).

  2. The robber then chooses a vertex.

  3. The cops and the robber then move alternately, starting with the cops. In a move, every cop (respectively the robber) stays put or moves to an adjacent vertex.

The cops win if at some point a cop occupies the robber’s vertex. The cop number c(G)c(G) is the least kk such that kk cops have a strategy that wins against every robber. In the lazy variant at most one cop moves on each cop turn [9]. The lazy cop number cL(G)c_L(G) is defined in the same way. Clearly c(G)≤cL(G)c(G) \le c_L(G).

A position (C,r)(C,r) consists of the multiset CC of cop vertices and the robber’s vertex rr, with the cops about to move. To show that kk cops do not suffice we use the following standard principle.

Lemma 2.1. Let SS be a set of positions for kk cops such that:

(a) (placement) for every CC there is an rr with (C,r)∈S(C,r) \in S;

(b) (safety) if (C,r)∈S(C,r) \in S then no cop of CC dominates rr;

(c) (closure) if (C,r)∈S(C,r) \in S and C′C' is obtained from CC by a cop move, then there is r′∈N[r]r' \in N[r] with (C′,r′)∈S(C',r') \in S.

Then the robber can evade kk cops forever, so c(G)>kc(G)>k.

Proof. The robber starts at a vertex given by (a) and then always replies as in (c). By (b), when the cops are about to move, none of them is on or next to the robber. So the cops’ move cannot reach the robber. After the robber’s reply the position is again in SS, so by (b) the robber is not standing on a cop.

Theorem 2.2 (Aigner–Fromme [1]). If GG has girth at least 5 and minimum degree at least 3, then c(G)≥3c(G) \ge3.

For completeness we recall the proof in the form we shall reuse.

Proof. Let SS be the set of positions in which no cop dominates the robber.

Closure. Suppose (C,r)∈S(C,r) \in S and the cops move to C′C'. No cop of C′C' is on rr. Let c≠rc \ne r be a vertex. If N[c]N[c] contained two neighbours x≠yx \ne y of rr, there are two cases.

  • If c∈{x,y}c \in\{x,y\}, then r,x,yr,x,y span a triangle.

  • Otherwise rxcyr x c y is a 4-cycle.

Both are impossible. So each cop dominates at most one of the at least three neighbours of rr. The robber moves to an undominated neighbour, and the new position is in SS.

Placement. Here we need a vertex dominated by neither cop. For a cubic graph with more than 8 vertices one exists, since two closed neighbourhoods contain at most 8 vertices. (For JnJ_n see also Lemma 3.2(c).)

Lemma 2.1 now applies with $k=2.

Flower snarks

Definition 3.1 ([5]). Let n≥3n \ge3. The graph JnJ_n has the 4n4n vertices aia_i, bib_i, cic_i, did_i with 0≤i≤n−10 \le i \le n-1, and the following edges (indices of bb taken modulo nn):

  • aibia_i b_i, aicia_i c_i, aidia_i d_i for every ii (the claws);

  • bibi+1b_i b_{i+1} for every ii (the inner nn-cycle);

  • cici+1c_i c_{i+1} and didi+1d_i d_{i+1} for 0≤i≤n−20 \le i \le n-2, together with cn−1d0c_{n-1}d_0 and dn−1c0d_{n-1}c_0 (the outer 2n2n-cycle c0c1⋯cn−1d0d1⋯dn−1c0c_0c_1\cdots c_{n-1}d_0d_1\cdots d_{n-1}c_0).

For odd nn, JnJ_n is the flower snark.

The column of a vertex xi∈{ai,bi,ci,di}x_i \in\{a_i,b_i,c_i,d_i\} is π(xi)=i∈Zn\pi(x_i)=i \in\mathbb{Z}_n.

Lemma 3.2. Let n≥3n \ge3.

(a) N[ai]N[a_i] is exactly column ii, and every edge of JnJ_n joins two vertices whose columns are equal or differ by ±1\pm1 modulo nn.

(b) If n≥5n \ge5, then JnJ_n has girth at least 5 (in fact 5 for n=5n=5 and 6 for n≥7n \ge7).

(c) Every closed neighbourhood contains at most one vertex of {a0,…,an−1}\{a_0,\ldots,a_{n-1}\}.

Proof. (a) The first claim is immediate. Claws stay inside a column. The edges bibi+1b_i b_{i+1}, cici+1c_i c_{i+1} and didi+1d_i d_{i+1} join consecutive columns, and the two twist edges join column n−1n-1 to column 0.

(c) The aa-vertices are pairwise non-adjacent, and each other vertex has exactly one aa-neighbour.

(b) We show that no cycle of length at most 4 passes through an aa-vertex. Cycles avoiding the aa-vertices lie in the inner nn-cycle or the outer 2n2n-cycle, so they are long.

Suppose a short cycle passes through aia_i, with cycle-neighbours x≠yx \ne y in {bi,ci,di}\{b_i,c_i,d_i\}.

  • These three vertices are pairwise non-adjacent, so the cycle is not a triangle.

  • For a 4-cycle, xx and yy would need a common neighbour z≠aiz \ne a_i. Apart from aia_i, the neighbours of bib_i are bb-vertices, while those of ci,dic_i,d_i lie on the outer cycle. So {x,y}={ci,di}\{x,y\}=\{c_i,d_i\}, and zz is on the outer cycle.

  • On the outer $2n$-cycle, cic_i and did_i are at positions ii and n+in+i. A common neighbour would require n≡±2(mod2n)n \equiv\pm2 \pmod{2n}, which is impossible for $n \ge 3.

Figure 1. The flower snark J5J_5. The dashed edges c4d0c_4d_0 and d4c0d_4c_0 join the cc-path and the dd-path into one 10-cycle. Column ii is the claw {ai,bi,ci,di}\{a_i,b_i,c_i,d_i\}.

  • Finally, the inner and outer cycles have lengths n≥5n \ge5 and 2n≥102n \ge10.

The exact values of the girth were confirmed by computer for n≤41n \le41. □

The lower bound

Proposition 3.3. For n≥5n \ge5, two cops cannot catch the robber on JnJ_n. Hence c(Jn)≥3c(J_n) \ge3.

Proof. JnJ_n is cubic with girth at least 5 by Lemma 3.2(b), so Theorem 2.2 applies. For placement, two cops dominate at most two of a0,a1,a2a_0,a_1,a_2 by Lemma 3.2(c), and the robber starts on the third. □

The hypothesis n≥5n \ge5 is needed. J3J_3 contains the triangle b0b1b2b_0b_1b_2, and J4J_4 contains the 4-cycle b0b1b2b3b_0b_1b_2b_3.

The upper bound: the rolling wall

We prove the upper bound for a class of graphs that contains every JnJ_n.

Definition 3.4. A cyclic dominated decomposition of a graph GG into nn columns is a map π:V(G)→{0,…,n−1}\pi: V(G) \to\{0,\ldots,n-1\} together with vertices a0,…,an−1a_0,\ldots,a_{n-1} such that:

(i) each vertex vv is dominated by aπ(v)a_{\pi(v)};

(ii) every edge uvuv satisfies ∣π(u)−π(v)∣≤1|\pi(u)-\pi(v)| \le1, or {π(u),π(v)}={0,n−1}\{\pi(u),\pi(v)\} = \{0,n-1\}.

By Lemma 3.2(a), the columns of JnJ_n form such a decomposition. Its key consequence is the following.

A cop on aja_j is a wall. If the robber ever enters column jj, he is next to that cop, who captures him on the following move. Hence a robber who wants to survive never enters column jj.

Lemma 3.5 (Rolling wall). If GG is connected and has a cyclic dominated decomposition, then three cops win on GG. They win even in the lazy game, so c(G)≤cL(G)≤3c(G) \le c_L(G) \le3.

Proof. Call the cops WW, FF and MM (back wall, front wall, mover). All three start on a0a_0.

  • Throughout, if the robber is dominated by some cop at the start of a cop turn, that cop moves onto him and the game ends.

  • Otherwise exactly one cop moves, as described below. So the strategy is lazy.

We keep an integer ff, initially 0, and maintain the following.

Invariant. At each cop turn, WW is on a0a_0, FF is on afa_f, and the robber is in a column in {f+1,…,n−1}\{f+1,\ldots,n-1\}.

The invariant holds at the start. After the robber places, either he is in column 0 and is caught at once, or he is in a column in {1,…,n−1}\{1,\ldots,n-1\}.

The robber cannot leave the interval. Suppose the invariant holds and only MM moves. If the robber steps out of {f+1,…,n−1}\{f+1,\ldots,n-1\}, then by (ii) he enters column ff or column 0. There he is dominated by FF or WW, by (i), and is captured on the next turn.

A phase. By connectivity, MM walks along a path to af+1a_{f+1}, one edge per turn, while WW and FF stand still. During the walk the invariant is preserved, by the previous paragraph. When MM arrives on af+1a_{f+1} there are two cases.

  • If the robber is in column f+1f+1, MM dominates him and captures him.

  • Otherwise he is in a column in {f+2,…,n−1}\{f+2,\ldots,n-1\}.

We now rename the cops: MM becomes the new front wall, FF becomes the new mover, and ff increases by one. The invariant holds again.

Termination. Each phase is finite and increases ff. When f=n−1f=n-1 the interval {f+1,…,n−1}\{f+1,\ldots,n-1\} is empty, so the robber must already have been caught. □

Proof of Theorem 1.2. For n≥5n \ge5, Proposition 3.3 gives c(Jn)≥3c(J_n) \ge3. Lemmas 3.5 and 3.2(a) give cL(Jn)≤3c_L(J_n) \le3. Since c≤cLc \le c_L, both are equal to 3.

For n=3n=3, exhaustive computation (§ 5) shows that one cop loses and two cops win on J3J_3. Two independent programs agree on this. □

Remark 3.6. The strategy is wasteful. Each phase moves MM from af−1a_{f-1} to af+1a_{f+1} in four steps (via bf−1,bf,bf+1b_{f-1},b_f,b_{f+1}), and its worst-case capture time is exactly 4n−54n-5 (computed for odd n≤151n \le151). The optimal capture time with three cops is much smaller, roughly n/2n/2 (Table 1).

nn57911131517192123
capture time23456788910
nn252729313335373941
capture time111113131415161618

Table 1. Optimal three-cop capture time on JnJ_n, measured in cop moves. For every odd n≤41n \le41, two cops lose and three cops win; J3J_3 has cop number 2.

The decomposition idea is close to standard “guard a separator” arguments; compare the proof of c(G)≤tw⁡(G)/2+1c(G) \le\operatorname{tw}(G)/2+1 in [6]. We have not found Lemma 3.5 stated in the literature, but we do not claim the technique is new.

Generalized Petersen graphs with cop number two

For n≥3n \ge3 and 1≤k<n/21 \le k < n/2, the generalized Petersen graph GP⁡(n,k)\operatorname{GP}(n,k) [12] has outer vertices uju_j and inner vertices vjv_j (j∈Znj \in\mathbb{Z}_n). Its edges are ujuj+1u_ju_{j+1}, ujvju_jv_j and vjvj+kv_jv_{j+k}. Thus

N[uj]={uj−1,uj,uj+1,vj},N[vj]={vj,vj+k,vj−k}.N[u_j]=\{u_{j-1},u_j,u_{j+1},v_j\}, \qquad N[v_j]=\{v_j,v_{j+k},v_{j-k}\}.

Lemma 4.1 (cf. [2]). Let 2≤k<n/22 \le k < n/2. Then GP⁡(n,k)\operatorname{GP}(n,k) has girth at most 4 if and only if n=3kn=3k or n=4kn=4k.

Proof. Every cycle uses an even number of spokes ujvju_jv_j. Consider the short cycles by the number of spokes they use.

  • No spokes. The cycle lies in the outer nn-cycle, so its length is n≥5n \ge5; or it lies in the inner graph. A short inner cycle needs 3k≡03k \equiv0 or 4k≡0(modn)4k \equiv0 \pmod n. Since 2k<n2k<n, this means n=3kn=3k or n=4kn=4k.

  • Two spokes, length 4. The cycle is ujuj±1vj±1vju_j u_{j\pm1}v_{j\pm1}v_j, which needs k≡±1(modn)k \equiv\pm1 \pmod n. That is excluded.

  • Two spokes, length 3. This is impossible.

Theorem 4.2. If k≥4k \ge4, two cops cannot catch the robber on GP⁡(3k,k)\operatorname{GP}(3k,k) or on GP⁡(4k,k)\operatorname{GP}(4k,k).

We first show how Theorem 1.4 follows.

Proof of Theorem 1.4 from Theorem 4.2. The listed graphs have cop number 2.

  • For GP⁡(n,1)\operatorname{GP}(n,1), GP⁡(6,2)\operatorname{GP}(6,2) and GP⁡(8,2)\operatorname{GP}(8,2) this is in [2] (by hand).

  • For GP⁡(9,3)\operatorname{GP}(9,3) and GP⁡(12,3)\operatorname{GP}(12,3) it is also in [2] (by computer). We confirmed all four of the small cases with two independent solvers.

Now let 2≤k<n/22 \le k < n/2 with (n,k)(n,k) not listed. There are two cases.

  • If n∉{3k,4k}n \notin\{3k,4k\}, then GP⁡(n,k)\operatorname{GP}(n,k) is cubic of girth at least 5 by Lemma 4.1, so c≥3c \ge3 by Theorem 2.2. Placement holds since 2n>82n > 8.

  • Otherwise k≥4k \ge4, and c≥3c \ge3 by Theorem 4.2.

The safe set

Fix n=3kn=3k or n=4kn=4k with k≥4k \ge4. For an index ii put Ui={ui−1,ui,ui+1}U_i=\{u_{i-1},u_i,u_{i+1}\} and

Bi={ui−2,ui−1,ui+1,ui+2,vi−1,vi+1}.B_i=\{u_{i-2},u_{i-1},u_{i+1},u_{i+2},v_{i-1},v_{i+1}\}.

A cop that can step into UiU_i in one move and is not in N[vi]N[v_i] lies in BiB_i. We also define

Ai={{ui−k,ui+k}if n=3k,{vi+2k,ui+2k}if n=4k.A_i= \begin{cases} \{u_{i-k},u_{i+k}\} & \text{if } n=3k,\\ \{v_{i+2k},u_{i+2k}\} & \text{if } n=4k. \end{cases}

Let TiT_i denote the inner triangle {vi,vi+k,vi−k}\{v_i,v_{i+k},v_{i-k}\} when n=3kn=3k, and let wi=vi+2kw_i=v_{i+2k} be the antipode of viv_i on its inner 4-cycle when n=4kn=4k. Then AiA_i is the set of vertices outside N[vi]N[v_i] from which a cop can step onto a vertex dominating both inner neighbours of viv_i: a vertex of TiT_i, or wiw_i.

Let S\mathcal{S} be the set of positions ({c1,c2},r)(\{c_1,c_2\},r) such that:

(S1) no cop dominates rr; and

(S2) if r=vir=v_i is an inner vertex, it is not the case that one cop is in AiA_i and the other is in BiB_i.

In words, a robber on viv_i is threatened only if one cop guards the exit to the outer rim while the other guards both inner exits. (S2) forbids exactly this combination.

Index facts

Put Di=TiD_i=T_i if n=3kn=3k, and Di={vi,wi}D_i=\{v_i,w_i\} if n=4kn=4k. All indices are modulo nn, and ee ranges over {−1,0,1}\{-1,0,1\}. Each fact below says that some small integer combination of kk is not ≡0(modn)\equiv0 \pmod n. Each is checked directly and holds under the stated hypothesis.

(F1) vi±1∉N[vi]v_{i\pm1}\notin N[v_i], and ui+e∉N[vi±k]u_{i+e}\notin N[v_{i\pm k}] (k≥2)(k\ge2).

(F2) Ai∩Bi=∅A_i\cap B_i=\varnothing (k≥3)(k\ge3).

(F3) N[vi+k]∩N[vi−k]=DiN[v_{i+k}]\cap N[v_{i-k}]=D_i, and N[Di]∖N[vi]=AiN[D_i]\setminus N[v_i]=A_i (k≥2)(k\ge2).

(F4) ui+e∉Bi+k∪Bi−ku_{i+e}\notin B_{i+k}\cup B_{i-k} (k≥4)(k\ge4).

(F5) N[vi±k]∖DiN[v_{i\pm k}]\setminus D_i is disjoint from Bi∓kB_{i\mp k}. This set is {ui±k}\{u_{i\pm k}\} if n=3kn=3k, and {vi±k,ui±k}\{v_{i\pm k},u_{i\pm k}\} if n=4kn=4k (k≥3)(k\ge3).

(F6) Bi+k∩Bi−k=∅B_{i+k}\cap B_{i-k}=\varnothing (k≥5 if n=3k; k≥3 if n=4k)(k\ge5\text{ if }n=3k;\ k\ge3\text{ if }n=4k).

For example:

  • (F4) fails only if ui+e=ui±k+δu_{i+e}=u_{i\pm k+\delta} with ∣δ∣≤2|\delta|\le2. That forces k≡m(modn)k\equiv m\pmod n with ∣m∣≤3|m|\le3, which is impossible for k≥4k\ge4.

  • (F6) fails only if 2k≡m(modn)2k\equiv m\pmod n with ∣m∣≤4|m|\le4. For n=3kn=3k this forces k≤4k\le4, and indeed (F6) fails for GP⁡(12,4)\operatorname{GP}(12,4), where ui+6=ui−6u_{i+6}=u_{i-6}.

Proof of Theorem 4.2

We verify the three conditions of Lemma 2.1. Safety is (S1).

Placement.

  • A cop on umu_m dominates three outer vertices, and a cop on vmv_m dominates one.

  • Since n>6n > 6, some outer vertex is undominated. (S2) is vacuous there.

Closure. Let (C,r)∈S(C,r) \in S, and let the cops move to C′C'. We write X′X' for the new position of a cop XX.

Case 1: r=uir = u_i. No cop of C′C' is on uiu_i.

If some vertex of UiU_i is undominated by C′C', the robber moves there.

Otherwise, since n≥5n \ge5, the only vertices other than uiu_i that dominate two vertices of UiU_i are ui−1u_{i-1} and ui+1u_{i+1}. So one cop is on, say, ui+1u_{i+1}, and the other dominates ui−1u_{i-1} without being on uiu_i. Hence both cops lie in BiB_i. The robber moves to viv_i.

  • (S1) holds by (F1).

  • (S2) holds because Ai∩Bi=∅A_i \cap B_i = \varnothing (F2), so neither cop is in AiA_i.

Case 2: r=vir = v_i. By (S1) no cop of CC is in N[vi]N[v_i], so no cop of C′C' is on viv_i.

Case 2a. If no cop of C′C' is in UiU_i, then uiu_i is undominated, and the robber moves to uiu_i.

Case 2b. Otherwise, let XX be a cop with X′∈UiX' \in U_i, and let YY be the other cop.

  • XX was in N[Ui]∖N[vi]=BiN[U_i] \setminus N[v_i] = B_i.

  • So, by (S2) for (C,vi)(C,v_i), YY was not in AiA_i. By (S1), YY was not in N[vi]N[v_i] either.

  • By (F1) and (F4), X′X' dominates neither vi+kv_{i+k} nor vi−kv_{i-k}, and X′∉Bi+k∪Bi−kX' \notin B_{i+k} \cup B_{i-k}.

We claim that there is t∈{vi+k,vi−k}t \in\{v_{i+k},v_{i-k}\} that Y′Y' does not dominate and with Y′∉BtY' \notin B_t.

  • First, Y′∉DiY' \notin D_i. Otherwise Y∈N[Di]∖N[vi]=AiY \in N[D_i] \setminus N[v_i] = A_i by (F3).

  • Hence, by (F3), Y′Y' dominates at most one of vi±kv_{i\pm k}.

  • If Y′Y' dominates vi±kv_{i\pm k}, then Y′∈N[vi±k]∖DiY' \in N[v_{i\pm k}] \setminus D_i. Take t=vi∓kt = v_{i\mp k}, so Y′∉BtY' \notin B_t by (F5).

  • If Y′Y' dominates neither, then by (F6) Y′Y' lies outside at least one of Bi+kB_{i+k} and Bi−kB_{i-k}. Take tt to be the corresponding vertex.

The robber moves to tt, which is legal since t∈N[vi]t \in N[v_i].

  • (S1) holds at tt, since neither cop dominates it.

  • (S2) holds at tt, since neither cop is in BtB_t.

This proves closure for GP⁡(3k,k)\operatorname{GP}(3k,k) with k≥5k \ge5 and for GP⁡(4k,k)\operatorname{GP}(4k,k) with k≥4k \ge4.

The case GP⁡(12,4)\operatorname{GP}(12,4). Here (F6) fails, and so does the claim in Case 2b. We use instead the safe set S12S_{12} obtained from SS by also forbidding, for a robber on viv_i, the eight cop pairs

{ui±1,ui±5} (four pairs),{ui±1,ui+6},{ui±1,vi+6}.\{u_{i\pm1},u_{i\pm5}\}\ \text{(four pairs)},\qquad\{u_{i\pm1},u_{i+6}\},\qquad\{u_{i\pm1},v_{i+6}\}.

A direct enumeration of all 300 cop placements and 24 robber vertices verifies conditions (a)–(c) of Lemma 2.1 for S12S_{12}. This finishes the proof. □

Remark 4.3. For every k≤40k \le40, the set SS (respectively S12S_{12}) coincides exactly with the set of positions from which the robber can evade two cops, as computed by an exhaustive solver. The robber’s replies described above were also replayed mechanically against every cop move for k≤30k \le30.

Computations

We computed the outcome of the game by retrograde analysis of the game graph, which gives the exact winning region and the exact capture time. Two independent programs were used. They share no code, and each builds the graphs from the definitions. They agree on every case that both computed.

  • Flower snarks. Two cops lose and three cops win on JnJ_n for every odd 5≤n≤415 \le n \le41. One cop loses and two cops win on J3J_3. The lazy cop number of JnJ_n is 3 for n∈{3,5,7,9}n \in\{3,5,7,9\}; note that cL(J3)=3>c(J3)c_L(J_3) = 3 > c(J_3).

  • Generalized Petersen graphs. Two cops lose on GP⁡(3k,k)\operatorname{GP}(3k,k) and GP⁡(4k,k)\operatorname{GP}(4k,k) for 4≤k≤404 \le k \le40 (up to 320 vertices), and three cops win for k≤20k \le20. Two cops win for k∈{2,3}k \in\{2,3\}.

Formal verification

The statement

∀n≥5,copNumber⁡(Jn)=3\forall n \ge5,\quad\operatorname{copNumber}(J_n) = 3

is proved in Lean 4 using Mathlib [4, 11]. The proof assistant reports that it depends only on the standard axioms (propositional extensionality, choice and quotient soundness). It uses no computer search.

  • The game. A position is cop-winning if it lies in the least set of positions that is closed under “the cops can move so that every robber reply leads into the set”. Defined this way, a winning position means capture is forced in finitely many moves.

  • Robber wins. These are certified by a safe set as in Lemma 2.1. We prove that the two notions exclude each other.

  • The lower bound. This is the argument of Theorem 2.2. The local facts for JnJ_n are discharged by linear arithmetic, uniformly in nn.

  • The upper bound. This is Lemma 3.5, proved for an abstract cyclic dominated decomposition. The proof is by induction on the number of remaining columns, with an inner induction on the walk taken by the mover.

  • Fidelity of the definition. The formal definition of JnJ_n follows Definition 3.1 literally. Its edge set was exported and checked to be isomorphic to the graphs used in § 5.

The results of § 4 are formalised in the same development. The formal statement says that if k≥2k \ge2, 2k<n2k < n and (n,k)∉{(6,2),(8,2),(9,3),(12,3)}(n,k) \notin\{(6,2),(8,2),(9,3),(12,3)\}, then every winning team of cops on GP⁡(n,k)\operatorname{GP}(n,k) has at least three cops. Hence copNumber⁡(GP⁡(n,k))≥3\operatorname{copNumber}(\operatorname{GP}(n,k)) \ge3.

  • Girth at least 5. When n∉{3k,4k}n \notin\{3k,4k\}, the hypotheses of the Aigner–Fromme argument are again proved by linear arithmetic. The four graphs with n<9n < 9 are handled by direct evaluation.

  • GP⁡(3k,k)\operatorname{GP}(3k,k) and GP⁡(4k,k)\operatorname{GP}(4k,k). The safe set SS and the case analysis of § 4 are formalised uniformly in kk.

  • GP⁡(12,4)\operatorname{GP}(12,4). The certificate S12S_{12} is checked by the Lean kernel itself. This is a kernel evaluation, not compiled code, so it adds no axioms.

  • Axioms and fidelity. All of these theorems depend only on the three standard axioms. The formal GP⁡(n,k)\operatorname{GP}(n,k) was checked to have exactly the textbook edge set for several (n,k)(n,k).

The matching upper bounds (c=2c = 2 for the listed graphs, from [2]) are not formalised.

Concluding remarks

  1. Capture time. The optimal capture time of three cops on JnJ_n grows roughly like n/2n/2, but irregularly (Table 1). What is it exactly?

  1. Lazy cops. Theorem 1.2 determines the lazy cop number of JnJ_n, giving a partial answer to the snark analogue of [7 Problem 6.3]. The lazy cop number of generalized Petersen graphs remains open.

  1. Dominated decompositions. Lemma 3.5 applies to any graph that maps onto a cycle with dominated fibres. Which other snark families, or other cubic graphs, admit such a decomposition, possibly after contracting a bounded set?

Acknowledgements

Anthropic Claude assisted with proof-strategy exploration, manuscript drafting, computational checks, and Lean formalization; the author takes responsibility for the results.

San José State University

Email address: [email protected]

References

  1. [1]M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Mathematics 8 (1984), no. 1, 1–12.DOI
  2. [2]Taylor Ball, Robert W. Bell, Jonathan Guzman, Madeleine Hanson-Colvin, and Nikolas Schonsheck, On the cop number of generalized Petersen graphs, Discrete Mathematics 340 (2017), no. 6, 1381–1388.arxiv.org/abs/1509.04696
  3. [3]Anthony Bonato and Richard J. Nowakowski, The game of cops and robbers on graphs, Student Mathematical Library, vol. 61, American Mathematical Society, Providence, RI, 2011.
  4. [4]Leonardo de Moura and Sebastian Ullrich, The Lean 4 theorem prover and programming language, Automated Deduction – CADE 28, Lecture Notes in Computer Science, vol. 12699, Springer, 2021, pp. 625–635.DOI
  5. [5]Rufus Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, The American Mathematical Monthly 82 (1975), no. 3, 221–239.DOI
  6. [6]Gwenaël Joret, Marcin Kamiński, and Dirk Oliver Theis, The cops and robber game on graphs with forbidden (induced) subgraphs, Contributions to Discrete Mathematics 5 (2010), no. 2.
  7. [7]Joy Morris, Tigana Runte, and Adrian Skelton, Most generalized Petersen graphs of girth 8 have cop number 4, Australasian Journal of Combinatorics 83 (2022), no. 2, 204–224.
  8. [8]Richard Nowakowski and Peter Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics 43 (1983), no. 2–3, 235–239.DOI
  9. [9]David Offner and Kerry Ojakian, Variations of cops and robber on the hypercube, Australasian Journal of Combinatorics 59 (2014), no. 2, 229–250.
  10. [10]AI-generated exploration of the cop number of the flower snarks, ProbXiv, https://probxiv.com/problems/most-generalized-petersen-graphs-of-girth-8-have-cop-number-4-3, 2026, Public comment dated 17 August 2026; the page states that no person has examined it.
  11. [11]The mathlib Community, The Lean mathematical library, Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), 2020, pp. 367–381.DOI
  12. [12]Mark E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, Journal of Combinatorial Theory 6 (1969), 152–164.DOI

Paper details

vlnc:W_b2n3rfqr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Anthropic Claude

View statement
Looking for related papers…
Contents