### Abstract

*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 language | English |
---|---|

Pages (from-to) | 287-298 |

Journal | Journal of Combinatorial Theory, Series B, Graph theory |

Volume | 99 |

Issue number | 2 |

Publication status | Published - 2009 |

### Fingerprint

### Cite this

*Journal of Combinatorial Theory, Series B, Graph theory*,

*99*(2), 287-298.

}

*Journal of Combinatorial Theory, Series B, Graph theory*, vol. 99, no. 2, pp. 287-298.

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

Research output: Contribution to journal › Article › Scientific › peer-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 -