Upper bound for the Laplacian eigenvalues of a graph

Abstract

In this note we give a new upper bound for the Laplacian eigenvalues of an unweighted graph. Let $G$ be a simple graph on $n$ vertices. Let $d_m(G)$ and ${\lambda }_{m+1}(G)$ be the $m$-th smallest degree of $G$ and the $m+1$-th smallest Laplacian eigenvalue of $G$ respectively. Then ${\lambda }_{m+1}(G)\le d_m(G)+m-1$ for $\bar{G}\ne K_m+(n-m)K_1$. We also introduce upper and lower bound for the Laplacian eigenvalues of weighted graphs, and compare it with the special case of unweighted graphs.

3 pages