Toughness and spectral radius in graphs

Abstract

Let $t$ be a positive integer, and let $G$ be a connected graph of order $n$ with $n\ge t+2$. A graph $G$ is said to be $\frac{1}{t}$-tough if $|S|\ge \frac{1}{t}c(G-S)$ for every subset $S$ of $V(G)$ with $c(G-S)\ge 2$, where $c(G-S)$ is the number of connected components in $G-S$. The adjacency matrix of $G$ is denoted by $A(G)$. Let $\hat{I}{»}_1(G)\ge \hat{I}{»}_2(G)\ge \cdots \ge \hat{I}{»}_n(G)$ be the eigenvalues of $A(G)$. In particular, the eigenvalue $\hat{I}{»}_1(G)$ is called the spectral radius of $G$. In this paper, we prove that $G$ is a $\frac{1}{t}$-tough graph unless $G=K_1\vee (K_{n-t-1}\cup t{K}_1)$ if $\hat{I}{»}_1(G)\ge \hat{I}\cdot (t,n)$, where $\hat{I}\cdot (t,n)$ is the largest root of $x^3-(n-t-2)x^2-(n-1)x+t(n-t-2)=0$.

7 pages