← ALB News · curated headline

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

arXiv Mathematics · WORLD · Mathematics · 11/17/2026, 12:00:00 AM

arXiv:2611.18787v1 Announce Type: new 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.

Continue to arXiv Mathematics →

You are being forwarded in 6s — stay on this page