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?

Improve this question
$\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
    Commented 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$
    – Ken W. Smith
    Commented 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
    Commented Dec 5, 2014 at 16:11
  • $\begingroup$ Isn't it well known that any regular bipartite graph can be decomposed into perfect matchings? $\endgroup$
    – David Roberson
    Commented May 17, 2018 at 14:08

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Delio Mugnolo
    Commented 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$
    – Sebi Cioaba
    Commented 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$
    – Sebi Cioaba
    Commented 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .