Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657452 | Journal of Combinatorial Theory, Series B | 2007 | 4 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sebastian M. Cioabă, David A. Gregory, Vladimir Nikiforov,