Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4603679 | Linear Algebra and its Applications | 2007 | 10 Pages |
Abstract
We find lower bounds on the difference between the spectral radius λ1 and the average degree 2en of an irregular graph G of order n and size e. In particular, we show that, if n ⩾ 4, thenλ1-2en>1n(Δ+2),where ΔΔ is the maximum of the vertex degrees in G.Brouwer and Haemers found eigenvalue conditions sufficient to imply the existence of perfect matchings in regular graphs. Using the above bound, we refine and extend their results to obtain sufficient conditions for the existence of large matchings in regular graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Sebastian M. Cioabă, David A. Gregory,