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
m G ( x ) := ∑ k ≥ 0 m k x k . {\displaystyle m_{G}(x):=\sum _{k\geq 0}m_{k}x^{k}.}
Another definition gives the matching polynomial as
M G ( x ) := ∑ k ≥ 0 ( − 1 ) k m k x n − 2 k . {\displaystyle M_{G}(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}.}
A third definition is the polynomial
μ G ( x , y ) := ∑ k ≥ 0 m k x k y n − 2 k . {\displaystyle \mu _{G}(x,y):=\sum _{k\geq 0}m_{k}x^{k}y^{n-2k}.}
Each type has its uses, and all are equivalent by simple transformations. For instance,
M G ( x ) = x n m G ( − x − 2 ) {\displaystyle M_{G}(x)=x^{n}m_{G}(-x^{-2})}
and
μ G ( x , y ) = y n m G ( x / y 2 ) . {\displaystyle \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 = 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:
M K m , n ( x ) = n ! L n ( m − n ) ( x 2 ) . {\displaystyle M_{K_{m,n}}(x)=n!L_{n}^{(m-n)}(x^{2}).}
If G is the complete graph Kn, then MG(x) is an Hermite polynomial:
M K n ( x ) = H n ( x ) , {\displaystyle M_{K_{n}}(x)=H_{n}(x),}
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 the characteristic polynomial of its adjacency matrix. 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.
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 Zaslavsky (1981). The other is an integral identity due to Godsil (1981). There is a similar relation for a subgraph G of Km,n and its complement in Km,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 mG(1) (Gutman 1991). The third type of matching polynomial was introduced by Farrell (1980) 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 (Jerrum 1987). 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 (Courcelle, Makowsky & Rotics 2001). The matching polynomial of a graph with n vertices and clique-width k may be computed in time nO(k) (Makowsky et al. 2006).
… excerpt ends here. Continue reading the full article.
