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 n - 1 order when n is odd. We also examine how other eigenvalues affect the size of matchings in G.
Original language | English |
---|---|
Pages (from-to) | 287-298 |
Journal | Journal of Combinatorial Theory Series B |
Volume | 99 |
Issue number | 2 |
Publication status | Published - 2009 |