Spectral Threshold for Extremal Cyclic Edge-Connectivity

Abstract

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 that for graphs of minimum degree at least 3 and girth $g$ at least 4, the cyclic edge-connectivity is bounded above by $(\Delta -2)g$ where $\Delta$ is the maximum degree. We then prove that if the second eigenvalue of the adjacency matrix of a $d$-regular graph of girth $g\ge 4$ is sufficiently small, then the cyclic edge-connectivity is $(d-2)g$, providing a spectral condition for when this upper bound on cyclic edge-connectivity is tight.

11 pages, 2 figures; to appear in Graphs and Combinatorics