Article ID Journal Published Year Pages File Type
4657452 Journal of Combinatorial Theory, Series B 2007 4 Pages PDF
Abstract

Let λ1λ1 be the greatest eigenvalue and λnλn the least eigenvalue of the adjacency matrix of a connected graph G with n vertices, m edges and diameter D. We prove that if G is nonregular, thenΔ−λ1>nΔ−2mn(D(nΔ−2m)+1)⩾1n(D+1), where Δ is the maximum degree of G.The inequality improves previous bounds of Stevanović and of Zhang. It also implies that a lower bound on λnλn obtained by Alon and Sudakov for (possibly regular) connected nonbipartite graphs also holds for connected nonregular graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,