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. 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 ''m_k'' be the number of ''k''-edge matchings.

One matching polynomial of ''G'' is
:$m_G(x) := \sum_ m_k x^k.$

Another definition gives the matching polynomial as
:$M_G(x) := \sum_ (-1)^k m_k x^.$

A third definition is the polynomial
:$\mu_G(x,y) := \sum_ m_k x^k y^.$

Each type has its uses, and all are equivalent by simple transformations. For instance,
:$M_G(x) = x^n m_G(-x^)$
and
:$\mu_G(x,y) = y^n m_G(x/y^2).$

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:

: $M_(x) = n! L_n^(x^2). \,$

If ''G'' is the complete graph ''K''_''n'', then ''M''_''G''(''x'') is an Hermite polynomial:
: $M_(x) = H_n(x), \,$
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'') .

References

*.
*.
*.
*.
*.
*.
*.
*{{citation
, last = Zaslavsky , first = Thomas
, journal = European Journal of Combinatorics
, pages = 91–103
, title = Complementary matching vectors and the uniform matching extension property
, volume = 2
, year = 1981
, doi=10.1016/s0195-6698(81)80025-x, doi-access = free
.

Algebraic graph theory
Matching (graph theory)
Polynomials
Graph invariants