A lower bound of toughness of regular graphs: in terms of second largest eigenvalue

Abstract

Let $G$ be a connected (non-complete) $d$-regular graph with $d\ge 3$. Let $c(G-S)$ denote the number of components of $G-S$ for any cut $S$ of $G$. The toughness $t(G)$ of $G$ is defined as $\min \left\{\frac{|S|}{c(G-S)}\right\}$, where the minimum is taken over all proper cuts $S$ of $G$. Let ${\lambda }_2(G)$ denote the second largest eigenvalue of $G$. In this paper, we prove $$t(G)\ge \min \left\{\frac{d+1}{d}(d-{\lambda }_2(G)),1\right\}.$$