We study the game of Cops and Robbers, where cops try to capture a robber on the vertices of a graph. Meyniel's conjecture states that for every connected graph $G$ on $n$ vertices, the cop number of $G$ is upper bounded by $O(\sqrt{ n})$, i.e., that $O(\sqrt{ n})$ suffice to catch the robber. We present several families of abelian Cayley graphs that are Meyniel extremal, i.e., graphs whose cop number is $O(\sqrt{ n})$. This proves that the $O(\sqrt{ n})$ upper bound for Cayley graphs proved by Bradshaw is tight up to a multiplicative constant. In particular, this shows that Meyniel's conjecture, if true, is tight to a multiplicative constant even for abelian Cayley graphs. In order to prove the result, we construct Cayley graphs on $n$ vertices with $\Omega(\sqrt{ n})$ generators that are $K_{ 2,3}$-free. This shows that the K\"{ o}v\'{ a}ri, S\'{ o}s, and Tur\'{ a}n theorem, stating that any $K_{ 2,3}$-free graph of $n$ vertices has at most $O(n^{ 3/2})$ edges, is tight up to a multiplicative constant even for abelian Cayley graphs.
Categories: math.CO