论文标题
关于高腰间的COP数量
On the cop number of graphs of high girth
论文作者
论文摘要
我们在最低程度上，在一定的生长条件下为COP的高围绕高图的COP数量建立了一个下限。我们特别表明，带有Girth $ G $和最低度$δ$的任何图的COP号至少为$ \ tfrac {1} {g} {g}（δ-1）^{\ lfloor \ frac \ frac {g-1} {4} {4} {4} {4} \ rfloor} $。我们为有向图建立了相似的结果。虽然揭示了一些猜想的原因，该指数$ \ tfrac {1} {4} g $在此下限中不能改进到$（\ tfrac {1} {1} {4}+\ varepsilon）g $，我们也能够证明它不能超过$ \ \ frac {3} g $。这是通过考虑某种Ramanujan图表来确定的。在证明这一界限的证据中，我们还表明，“弱” Meyniel的猜想适用于有限程度的扩展器图。
We establish a lower bound for the cop number of graphs of high girth in terms of the minimum degree, and more generally, in terms of a certain growth condition. We show, in particular, that the cop number of any graph with girth $g$ and minimum degree $δ$ is at least $\tfrac{1}{g}(δ- 1)^{\lfloor \frac{g-1}{4}\rfloor}$. We establish similar results for directed graphs. While exposing several reasons for conjecturing that the exponent $\tfrac{1}{4}g$ in this lower bound cannot be improved to $(\tfrac{1}{4}+\varepsilon)g$, we are also able to prove that it cannot be increased beyond $\frac{3}{8}g$. This is established by considering a certain family of Ramanujan graphs. In our proof of this bound, we also show that the "weak" Meyniel's conjecture holds for expander graph families of bounded degree.
