Eigenvalues and perfect matchings

By Andries E. Brouwer, Willem H. Haemers. 2005

144 citations recorded by the source corpus.

We give sufficient conditions for existence of a perfect matching in a graph in terms of the eigenvalues of the Laplacian matrix. We also show that a distance-regular graph of degree k is k-edge-connected.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/d652d7f959f05f9077190d78815753d78bfb7032

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Weijun Liu
2. Yongtao Li
3. Lihua Feng
4. Sebastian M. Cioaba
5. David A. Gregory

In Geometry and Topology

1. Yongtao Li
2. Weijun Liu
3. Lihua Feng
4. Sebastian M. Cioaba
5. David A. Gregory
6. Vladimir Nikiforov

In Numerical Analysis

1. Sebastian M. Cioaba
2. David A. Gregory
3. Vladimir Nikiforov

Citations in the corpus

• Eigenvalues and edge-connectivity of regular graphs (2010, methodology): “Eigenvalue techniques have been also used recently by Brouwer and Koolen [5] to show that the vertex-connectivity of a distance-regular graph equals its degree (see also [2,4] for related results).”
• A survey on spectral conditions for some extremal graph problems (2021, background): “[27] Let G be a connected k-regular graph on n vertices with adjacency eigenvalues k = λ1 ≥ λ2 ≥ λ3 ≥ · · · ≥ λn.”
• Large matchings from eigenvalues (2007, methodology): “Brouwer and Haemers proved the following result in [2].”