1
$\begingroup$

Consider a graph $G$ with $n$ vertices. Let $m_k$ be the number of $k$-edge matchings. (A matching in a graph is a set of edges without common vertices.) Several different types of matching polynomials have been defined, but consider the following definition.

\begin{equation*} M_G(x) = \sum_{0\leq k}(-1)^k m_k x^{n-2k} \end{equation*}

According to the wikipedia article, the matching polynomial for $G=K_{m,n}$ (a complete bipartite graph) is related to the generalized Laguerre polynomial $L_n^{\alpha}(x)$:

\begin{equation*} M_{K_{m,n}} = n! L_n^{(m-n)}(x^2) \end{equation*}

How can I prove it? Is there any reference (paper or textbook) so that I can derive this relation myself?

$\endgroup$
2
$\begingroup$

This result was proved by Gutman in 1979, see http://match.pmf.kg.ac.rs/electronic_versions/Match06/match6_75-91.pdf It may also be in "Theory of monomer-dimer systems by Heilman and Lieb, but I do not have a copy of that at hand. Gutman shows that the matching polynomials of the complete bipartite graphs satisfies the same three-term recurrence as the generalized Laguerre polynomials. If you know the coefficients of the generalized Laguerre polynomial, the proof is trivial of course.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The following paper gives a bijective proof of some sort:

http://link.springer.com/chapter/10.1007%2FBFb0076537

I believe the Foata reference is where the identity was originally proved.

I don't want to repeat what's in the paper, but there are the references at least.

| cite | improve this answer | |
$\endgroup$

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.