Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the cop number of graphs of high girth   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 $\delta$ is at least $\tfrac{1}{g}(\delta - 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.

36
The categories of this paper are: cmp-lg
31
The categories of this paper are: ao-sci
0
The categories of this paper are: hep-ph
12
The categories of this paper are: nucl-th
23
The categories of this paper are: solv-int
11
The categories of this paper are: hep-lat
33
The categories of this paper are: plasm-ph
5
The categories of this paper are: gr-qc
24
The categories of this paper are: dg-ga
7
The categories of this paper are: hep-th
13
The categories of this paper are: quant-ph
25
The categories of this paper are: patt-sol
3
The categories of this paper are: physics
30
The categories of this paper are: q-alg
34
The categories of this paper are: chem-ph
15
The categories of this paper are: nucl-ex