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. It is one of several graph polynomials studied in algebraic graph theory.
Several different types of matching polynomials have been defined. Let G be a graph with n vertices and let m<sub>k</sub> 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 = K<sub>m,n</sub>, the complete bipartite graph, then the second type of matching polynomial is related to the generalized Laguerre polynomial L<sub>n</sub><sup>α</sup>(x) by the identity:
If G is the complete graph K<sub>n</sub>, then M<sub>G</sub>(x) is an Hermite polynomial:
where H<sub>n</sub>(x) is the "probabilist's Hermite polynomial" (1) in the definition of Hermite polynomials. These facts were observed by .
If G is a forest, then its matching polynomial is equal to the characteristic polynomial of its adjacency matrix.
If G is a path or a cycle, then M<sub>G</sub>(x) is a Chebyshev polynomial. In this case ü<sub>G</sub>(1,x) is a Fibonacci polynomial or Lucas polynomial respectively.
The matching polynomial of a graph G with n vertices is related to that of its complement by a pair of (equivalent) formulas. One of them is a simple combinatorial identity due to . The other is an integral identity due to .
There is a similar relation for a subgraph G of K<sub>m,n</sub> and its complement in K<sub>m,n</sub>. This relation, due to Riordan (1958), was known in the context of non-attacking rook placements and rook polynomials.
The Hosoya index of a graph G, its number of matchings, is used in chemoinformatics as a structural descriptor of a molecular graph. It may be evaluated as m<sub>G</sub>(1) .
The third type of matching polynomial was introduced by as a version of the "acyclic polynomial" used in chemistry.
On arbitrary graphs, or even planar graphs, computing the matching polynomial is #P-complete . However, it can be computed more efficiently when additional structure about the graph is known. In particular, computing the matching polynomial on n-vertex graphs of treewidth k is fixed-parameter tractable: there exists an algorithm whose running time, for any fixed constant k, is a polynomial in n with an exponent that does not depend on k . The matching polynomial of a graph with n vertices and clique-width k may be computed in time n<sup>O(k)</sup> .