Upper bound for the Laplacian eigenvalues of a graph

2011/06/03 by Farber, Miriam, Kaminer, Ido
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1106.0769

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 λ_m+1(G) be the m-th smallest degree of G and the m+1-th smallest Laplacian eigenvalue of G respectively. Then λ_m+1(G)≤ d_m(G)+m-1 for G ≠ K_m+(n-m)K₁ . We also introduce upper and lower bound for the Laplacian eigenvalues of weighted graphs, and compare it with the special case of unweighted graphs.

Related

• A lower bound of the least signless Laplacian eigenvalue of a graph
• Universal lower bounds for Laplacians on weighted graphs
• Combinatorial upper bounds for the smallest eigenvalue of a graph
• A few properties of the eigenvalues of normalized graph Laplacian
• Laplacian eigenvalue distribution for unicyclic graphs