The ℓ-toughness and eigenvalues of graphs

For an integer ℓ ≥ 2 , the ℓ -toughness τ ℓ ( G ) of a non-complete graph G = ( V ( G ) , E ( G ) ) is defined as τ ℓ ( G ) = min | S | c ( G − S ) : S ⊂ V ( G ) a n d c ( G − S ) ≥ ℓ , where c ( G − S ) is the number of components of G − S . We derive Laplacian eigenvalue lower bounds for τ ℓ ( G ) that depend on the component orders, and in particular on the number of isolated vertices, in a cut attaining τ ℓ ( G ) . These estimates are combined with the recent proof of Haemers’ toughness conjecture to give the stronger of a global bound and a component sensitive bound. We also determine, for sufficiently large order, the unique connected graph with prescribed integer ℓ -toughness that maximizes the adjacency spectral radius.