Matching polynomial of a complete bipartite graph is a generalized Laguerre polynomial.

Question

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?

Answer 1

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.

Answer 2

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.