The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:

Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-1}$ iff $G\cong K_n$ or $G\cong K_{p,q}$. Here $\lambda_1\ge\lambda_2\ge...\lambda_{n-1}\ge\lambda_{n}=0$ is the normalized Laplacian spectrum, i.e. the spectrum of the matrix $L^{sym}_G=D^{-1/2}L_GD^{-1/2}$.

The reference they give is rather difficult to locate. Can anyone give a reference or a detailed proof? Thanks.


1 Answer 1


Here is the link to paper in question: On the normalized Laplacian eigenvalues of graphs. Ars Comb.

Unfortunately only abstract seems to be available to the public

Let G = (V, E) be a simple connected graph with n vertices and m edges.
Further let λi(L), i = 1, 2, ., n, be the non-increasing eigenvalues of the normalized Laplacian matrix of the graph G. 
In this paper, we obtain the following result: 
For a connected graph G of order n, λ2(L) = λ3(L) = · = λn-1 (L)
if and only if G is a complete graph Kn or G is a complete bipartite graph Kp, q. 
Moreover, we present lower and upper bounds for the normalized Laplacian spectral radius of a graph and characterize graphs for which the lower or upper bounds is attained.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.