Toughness in regular graphs from eigenvalues

Abstract

The {\it toughness} $τ(G)=\mathrm{min}\{\frac{|S|}{c(G-S)}: S~\mbox{is a vertex cut in}~G\}$ for $G≆K_n,$ which was initially proposed by Chvátal in 1973. A graph $G$ is called {\it $t$-tough} if $\ddot{I}„(G)\ge t.$ Let $\hat{I}{»}_i(G)$ be the $i$-th largest eigenvalue of the adjacency matrix of a graph $G$. In 1996, Brouwer conjectured that $\ddot{I}„(G)\ge \frac{d}{\hat{I}}»-1$ for a connected $d$-regular graph $G,$ where $\hat{I}»=\max \{|\hat{I}{»}_2|,|\hat{I}{»}_n|\}.$ Gu [SIAM J. Discrete Math. 35 (2021) 948-952] completely confirmed this conjecture. From Brouwer and Gu's result $\ddot{I}„(G)\ge \frac{d}{\hat{I}}»-1,$ we know that if $G$ is a connected $d$-regular graph and $\hat{I}»\le \frac{bd}{b+1}$, then $\ddot{I}„(G)\ge \frac{1}{b}$ for an integer $b\ge 1.$ Inspired by the above result and utilizing typical spectral techniques and graph construction methods from Cioabă et al. [J. Combin. Theory Ser. B 99 (2009) 287-297], we prove that if $G$ is a connected $d$-regular graph and $\hat{I}{»}_2(G)<\ddot{I}•(d,b)$, then $\ddot{I}„(G)\ge \frac{1}{b}$. Meanwhile, we construct graphs implying that the upper bound on $\hat{I}{»}_2(G)$ is best possible. Our theorem strengthens the result of Chen et al. [Discrete Math. 348 (2025) 114404]. Finally, we also prove an upper bound of $\hat{I}{»}_{b+1}(G)$ to guarantee a connected $d$-regular graph to be $\frac{1}{b}$-tough.

23 pages, 4 figures