6
$\begingroup$

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?

$\endgroup$
4
  • 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, 2014 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$ Dec 5, 2014 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, 2014 at 16:11
  • $\begingroup$ Isn't it well known that any regular bipartite graph can be decomposed into perfect matchings? $\endgroup$ May 17, 2018 at 14:08

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2014 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$ Dec 9, 2014 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$ Dec 9, 2014 at 14:40
  • $\begingroup$ Now it is known that there are cospectral regular graphs with different edge-chromatic numbers, see the paper "The smallest pair of cospectral cubic graphs with different chromatic indexes" by Zhidan Yan, Wei Wang arxiv.org/abs/2112.06112 $\endgroup$ Dec 14, 2021 at 14:44
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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