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 :
بازگشت