Paperlane

no. 16 · Tuesday 17 November 2026

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

Aarav Ghai

math.CO · □ lean · 9 pp

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 $J_n$ has cop number $3$ for every $n\geq 5$, and that $J_3$ has cop number $2$. 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 $J_n$ is $3$ for $n\geq 5$. Second, we prove the conjecture of Morris, Runte and Skelton that the only generalized Petersen graphs with cop number $2$ are $\mathrm{GP}(n,1)$ and the four graphs $\mathrm{GP}(6,2)$, $\mathrm{GP}(8,2)$, $\mathrm{GP}(9,3)$ and $\mathrm{GP}(12,3)$. The new ingredient is an explicit robber strategy showing that two cops do not suffice on $\mathrm{GP}(3k,k)$ and $\mathrm{GP}(4k,k)$ for $k\geq 4$. The theorem on flower snarks and all of the new lower bounds have been formally verified in the Lean 4 proof assistant.

comments
9 pages, 1 figure, 1 table
fields
Combinatorics
pdf ↗ page arXiv:2611.18787 ↗