Spectral Threshold for Extremal Cyclic Edge-Connectivity

DOI10.1007/S00373-021-02333-6MaRDI QIDQ6336150arXivFDO

Authors Sinan Aksoy, Mark Kempton, Stephen J. Young

Publication date 4 March 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00373-021-02333-6

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

arXiv classification

math.CO

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 $ggeq4$ 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.

This page was built for publication: Spectral Threshold for Extremal Cyclic Edge-Connectivity

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