Matchings in regular graphs from eigenvalues

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

Research output: Contribution to journalArticleScientificpeer-review

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, Graph theory
Volume99
Issue number2
Publication statusPublished - 2009

Fingerprint

Regular Graph
Eigenvalue
Largest Eigenvalue
Perfect Matching
Odd
Sufficient
Upper bound

Cite this

@article{7208aebc184244e9ac5313abcd32fa78,
title = "Matchings in regular graphs from eigenvalues",
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.",
author = "S.M. Cioaba and D.A. Gregory and W.H. Haemers",
year = "2009",
language = "English",
volume = "99",
pages = "287--298",
journal = "Journal of Combinatorial Theory, Series B, Graph theory",
issn = "0095-8956",
publisher = "Academic Press Inc.",
number = "2",

}

Matchings in regular graphs from eigenvalues. / Cioaba, S.M.; Gregory, D.A.; Haemers, W.H.

In: Journal of Combinatorial Theory, Series B, Graph theory, Vol. 99, No. 2, 2009, p. 287-298.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Matchings in regular graphs from eigenvalues

AU - Cioaba, S.M.

AU - Gregory, D.A.

AU - Haemers, W.H.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

M3 - Article

VL - 99

SP - 287

EP - 298

JO - Journal of Combinatorial Theory, Series B, Graph theory

JF - Journal of Combinatorial Theory, Series B, Graph theory

SN - 0095-8956

IS - 2

ER -