Spectral Threshold for Extremal Cyclic Edge-Connectivity


The cyclic edge-connectivity of a graph $G$ is the least $k$ such that there exists a set of $k$ edges whose removal disconnects $G$ into components where every component contains a cycle. We show the cyclic edge-connectivity is defined for graphs with minimum degree at least 3 and girth at least 4, as long as $G$ is not $K_t,3$. From the proof of this result it follows that, other than $K_3,3$, the cyclic edge-connectivity is bounded above by $(d-2)g$ for $d$-regular graphs of girth $g ≥ 4$. We then provide a spectral condition for when this upper bound on cyclic edge-connectivity is tight.