论文标题
周长8的彼得森图最具广泛的彼得森图4
Most Generalized Petersen graphs of girth 8 have cop number 4
论文作者
论文摘要
广义的Petersen Graph $ GP（N，K）$是$ 2N $顶点（参数$ K $）的常规立方图（用于定义某些边缘）。以前已显示（Ball等，2015）$ GP（N，K）$的COP数量最多为$ 4 $，对于$ n $和$ k $的所有允许值。在本文中，我们证明了“大多数”广义Petersen图的COP数字正好为$ 4 $。更确切地说，我们表明，除非$ n $和$ k $属于某些指定类别，否则$ gp（n，k）$的COP号为$ 4 $。我们的结果适用的图形都带有周长$ 8 $。 实际上，我们的论点稍微更一般：我们表明，在任何立方图中，至少$ 8 $，除非存在两个长度的$ 8 $的循环，$ 8 $，其相交是长度为$ 2 $的路径，则该图的COP数量至少为$ 4 $。甚至更一般而言，在腰围至少$ 9 $和最低价值$δ$的图表中，COP号码至少为$δ+1 $。
A generalized Petersen graph $GP(n,k)$ is a regular cubic graph on $2n$ vertices (the parameter $k$ is used to define some of the edges). It was previously shown (Ball et al., 2015) that the cop number of $GP(n,k)$ is at most $4$, for all permissible values of $n$ and $k$. In this paper we prove that the cop number of "most" generalized Petersen graphs is exactly $4$. More precisely, we show that unless $n$ and $k$ fall into certain specified categories, then the cop number of $GP(n,k)$ is $4$. The graphs to which our result applies all have girth $8$. In fact, our argument is slightly more general: we show that in any cubic graph of girth at least $8$, unless there exist two cycles of length $8$ whose intersection is a path of length $2$, then the cop number of the graph is at least $4$. Even more generally, in a graph of girth at least $9$ and minimum valency $δ$, the cop number is at least $δ+1$.
