Title of article
Matchings in regular graphs from eigenvalues
Author/Authors
Melanie A. Adams-Cioaba، نويسنده , , Sebastian M. and Gregory، نويسنده , , David A. and Haemers، نويسنده , , Willem H.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
11
From page
287
To page
297
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.
Keywords
Matchings , eigenvalues , Spectral radius
Journal title
Journal of Combinatorial Theory Series B
Serial Year
2009
Journal title
Journal of Combinatorial Theory Series B
Record number
1528818
Link To Document