Maximum spectral gap of regular graphs with bounded essential edge-connectivity

Abstract

An edge-cut of a graph is said to be essential if its removal results in a graph with at least two non-trivial components. The essential edge-connectivity of a graph $G$ is the minimum cardinality among all essential edge-cuts of $G$. The spectral gap of $G$ is the difference between its largest and second largest eigenvalues. In this paper, we prove that for any integers $t$ and $r$ with $6\le r\le t\le 2r-3$, the maximum spectral gap among all connected $r$-regular graphs with essential edge-connectivity at most $t$ is equal to $\frac{1}{2}(r+7-\sqrt{(r+7{)}^2-8t-32})$ when $t-r$ is odd and $\frac{1}{2}(r+6-\sqrt{(r+6{)}^2-8t-32})$ when $t-r$ is even. We construct a family of connected $r$-regular graphs achieving these bounds.