| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4657142 | Journal of Combinatorial Theory, Series B | 2009 | 11 Pages |
Abstract
Let G be a connected k-regular graph of order n. We find a best upper bound (in terms of k) on the third largest eigenvalue that is sufficient to guarantee that G has a perfect matching when n is even, and a matching of order n−1 when n is odd. We also examine how other eigenvalues affect the size of matchings in G.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
