Matching polynomial
In the mathematical fields of graph theory and combinatorics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function of the numbers of matchings of various sizes in a graph.
Several different types of matching polynomials have been defined. Let G be a graph with n vertices and let mk be the number of k-edge matchings.
One matching polynomial of G is
Another definition gives the matching polynomial as
A third definition is the polynomial
Each type has its uses, and all are equivalent by simple transformations. For instance,
and
The first type of matching polynomial is a direct generalization of the rook polynomial.
The second type of matching polynomial has remarkable connections with orthogonal polynomials. For instance, if G = Km,n, the complete bipartite graph, then the second type of matching polynomial is related to the generalized Laguerre polynomial Lnα(x) by the identity:
If G is the complete graph Kn, then MG(x) is an Hermite polynomial:
where Hn(x) is the "probabilist's Hermite polynomial" (1) in the definition of Hermite polynomials. These facts were observed by Godsil (1981).
If G is a forest, then its matching polynomial is equal to its characteristic polynomial.
If G is a path or a cycle, then MG(x) is a Chebyshev polynomial. In this case μG(1,x) is a Fibonacci polynomial or Lucas polynomial respectively.
...
Wikipedia