• 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