Graphs with Large Girth and Small Cop Number

MaRDI QIDQ6438752zbMATH OpenFDO

Authors Alexander Clow

Publication date 31 May 2023

Mathematics Subject Classification ID

Expander graphs (05C48) Games on graphs (graph-theoretic aspects) (05C57) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper we consider the cop number of graphs with no, or few, short cycles. We show that when the girth of $G$ is at least $7$ and the minimum degree is sufficiently large, $deltageq(lnn{)}^{frac11-alpha}$ where $alphain(0,1)$, then $c(G)=o(ndelt{a}^{1-lfloorfracg4floor})$ as $nightarrowinfty$. This extends work of Frankl and implies that if $G$ is large and dense in the sense that $deltageq{n}^{frac2+o(1)g-1}$ while also having girth $ggeq7$, then $G$ satisfies Meyniel's conjecture, that is $c(G)=O(sqrtn)$. Moreover, it implies that if $G$ is large and dense in the sense that there $deltageq{n}^{epsilon}$ for some $epsilon>0$, while also having girth $ggeq7$, 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. We also, show that there are graphs $G$ with girth $g$ and minimum degree $delta$ such that the cop number is at most $o(g(delta-1{)}^{(1+o(1))fracg4})$. This resolves a recent conjecture by Bradshaw, Hosseini, Mohar, and Stacho, by showing that the constant $frac14$ cannot be improved in the exponent of a lower bound $c(G)geqfrac1g(delta-1{)}^{lfloorfracg-14floor}$.

This page was built for publication: Graphs with Large Girth and Small Cop Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438752)