Graphs with Large Girth and Small Cop Number

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 $δ\geq 2$, then $c(G) = O(n\log(n)(δ-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 $δ\geq n^{\frac{2}{g}+ε}$, 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 $δ\geq n^ε$, some $ε>0$, while also having girth $g \geq 7$, then there exists an $α>0$ such that $c(G) = O(n^{1-α})$, thereby satisfying the weak Meyniel's conjecture. Of course, this implies similar results for dense graphs with small, that is $O(n^{1-α})$, numbers of short cycles, as each cycle can be broken by adding a single cop.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.