If the edges of a bipartite graph are such that they can be seen as a disjoint union of perfect matchings then will this somehow reflect in the eigenvalues of the Laplacian?

It would be helpful to get any references which connect the concept of perfect matchings and graph eigenvalues...

Can something be said if the edges of the above bipartite graph decompose as a disjoint union of say $k$ perfect matchings and a part of another?

  • 1
    $\begingroup$ Brouwer, Andries E., and Willem H. Haemers. "Eigenvalues and perfect matchings." Linear Algebra and its Applications 395 (2005): 155-162. $\endgroup$ – Waldemar Dec 5 '14 at 8:49
  • $\begingroup$ Google the article above, "Eigenvalues and perfect matchings", mentioned by Waldemar, to find a pdf copy of it on ResearchGate. $\endgroup$ – Ken W. Smith Dec 5 '14 at 13:58
  • $\begingroup$ @Waldemar (and Ken W.Smith) Thanks for the reference. But this paper seems to go in the reverse direction than my question - right? Like this paper is a (sufficient) condition on the graph eigenvalues for a perfect matching to exist - but I want to know as to how does knowing the existence of perfect matchings help me with the eigenvalues.... $\endgroup$ – user6818 Dec 5 '14 at 16:11
  • $\begingroup$ Isn't it well known that any regular bipartite graph can be decomposed into perfect matchings? $\endgroup$ – David Roberson May 17 '18 at 14:08

Blazsik, Cummings and Haemers http://arxiv.org/abs/1409.0630 recently constructed two regular cospectral graphs such that one has a perfect matching and the other does not.

  • $\begingroup$ Thanks a lot for the link. SO this means that existence of perfect matchings have no bearing on the spectrum? Or is that too strong a conclusion? $\endgroup$ – user6818 Dec 9 '14 at 3:53
  • $\begingroup$ The quoted result still leaves open the question for the case of $r$-regular graphs, for $r=3,4$ (the case of $r=2$ being of course trivial). $\endgroup$ – Delio Mugnolo Dec 9 '14 at 11:23
  • $\begingroup$ The paper above shows that one perfect matching does not have much influence. It is still possible that perfect matchings (in larger number) could have an effect on eigenvalues. It is not known if there exist cospectral regular graphs with different edge-chromatic numbers. $\endgroup$ – Sebi Cioaba Dec 9 '14 at 14:40

In case of 3-regular (cubic) graphs there is a Petersen's theorem, stating that every 3-regular, 2-edge-connected (bridgeless) graph contains a perfect matching.

And there's also a paper by Sebastian M. Cioabă "Eigenvalues and edge-connectivity of regular graphs" that states a connection between the second largest eigenvalue of a d-regular graph and 2-edge-connectedness.

So, according to these results: if we have a 3-regular graph and the second largest eigenvalue is less than the largest root of $x^3 - 7x - 2 = 0$, then the graph is 2-edge-connected and it has a perfect matching.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.