Graph polynomial generating numbers of matchings
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.
Definition.
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
formula_1
Another definition gives the matching polynomial as
formula_2
A third definition is the polynomial
formula_3
Each type has its uses, and all are equivalent by simple transformations. For instance,
formula_4
and
formula_5
Connections to other polynomials.
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""m","n", the complete bipartite graph, then the second type of matching polynomial is related to the generalized Laguerre polynomial "L""n""α"("x") by the identity:
 formula_6
If "G" is the complete graph "K""n", then "M""G"("x") is an Hermite polynomial:
 formula_7
where "H""n"("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""G"("x") is a Chebyshev polynomial. In this case
μ"G"(1,"x") is a Fibonacci polynomial or Lucas polynomial respectively.
Complementation.
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""m","n" and its complement in "K""m","n". This relation, due to Riordan (1958), was known in the context of non-attacking rook placements and rook polynomials.
Applications in chemical informatics.
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""G"(1) .
The third type of matching polynomial was introduced by as a version of the "acyclic polynomial" used in chemistry.
Computational complexity.
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"O("k") .