Matchings in regular graphs from eigenvalues

S.M. Cioaba, D.A. Gregory, W.H. Haemers

Research output: Contribution to journalArticleScientificpeer-review

76 Citations (Scopus)

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 languageEnglish
Pages (from-to)287-298
JournalJournal of Combinatorial Theory Series B
Volume99
Issue number2
Publication statusPublished - 2009

Fingerprint

Dive into the research topics of 'Matchings in regular graphs from eigenvalues'. Together they form a unique fingerprint.

Cite this