# 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.

## Contents

## Definition

Several different types of matching polynomials have been defined. Let *G* be a graph with *n* vertices and let *m _{k}* 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

## 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:

If *G* is the complete graph *K*_{n}, then *M*_{G}(*x*) is an Hermite polynomial:

where *H*_{n}(*x*) is the "probabilist's Hermite polynomial" (1) in the definition of Hermite polynomials. These facts were observed by Template:Harvtxt.

If *G* is a forest, then its matching polynomial is equal to its characteristic polynomial.

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 Template:Harvtxt. The other is an integral identity due to Template:Harvtxt.

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) Template:Harv.

The third type of matching polynomial was introduced by Template:Harvtxt 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 Template:Harv. 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* Template:Harv.
The matching polynomial of a graph with *n* vertices and clique-width *k* may be computed in time *n*^{O(k)} Template:Harv

## References

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.