Graph toughness from Laplacian eigenvalues
Graph toughness from Laplacian eigenvalues
The toughness t(G) of a graph G=(V,E) is defined as t(G)=min|S| c(G-S), in which the minimum is taken over all S⊂V such that G-S is disconnected, where c(G-S) denotes the number of components of G-S. We present two tight lower bounds for t(G) in terms of the Laplacian eigenvalues and …