Graphs with Large Girth and Small Cop Number

Abstract

In this paper we consider the cop number of graphs with no, or few, short cycles. We show that when $G$ is graph of girth $g$ and the minimum degree $\delta \ge 2$, then $c(G)=O(n\log (n)(\delta -1{)}^{-\lfloor \frac{g+1}{4}\rfloor })$ as a function of $n$. This extends work of Frankl and implies that if $G$ is large and dense in the sense that $\delta \ge n^{\frac{2}{g}+\epsilon }$, then $G$ satisfies Meyniel's conjecture, that is $c(G)=O(\sqrt{n})$. Moreover, it implies that if $G$ is large and dense in the sense that there $\delta \ge n^{\epsilon }$, some $\epsilon >0$, while also having girth $g\ge 7$, then there exists an $\alpha >0$ such that $c(G)=O(n^{1-\alpha })$, thereby satisfying the weak Meyniel's conjecture. Of course, this implies similar results for dense graphs with small, that is $O(n^{1-\alpha })$, numbers of short cycles, as each cycle can be broken by adding a single cop.

arXiv comment7 pages, 0 figures, 0 tables