Cages and cyclic connectivity

Abstract

A graph $G$ is cyclically $c$-edge-connected if there is no set of fewer than $c$ edges that disconnects $G$ into at least two cyclic components. We prove that if a $(k,g)$-cage $G$ has at most $2M(k,g)-g^2$ vertices, where $M(k,g)$ is the Moore bound, then $G$ is cyclically $(k-2)g$-edge-connected, which equals the number of edges separating a $g$-cycle, and every cycle-separating $(k-2)g$-edge-cut in $G$ separates a cycle of length $g$. In particular, this is true for unknown cages with $(k,g)\in \{(3,13),(3,14),(3,15),(4,9),(4,10)$, $(4,11),$ $(5,7),(5,9),(5,10),(5,11),(6,7),(9,7)\}$ and also the potential missing Moore graph with degree $57$ and diameter $2$. Keywords: cage, cyclic connectivity, girth, lower bound