 Matching polynomial

In graph theory and combinatorics, both fields within mathematics, 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 kedge 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,
 M_{G}(x) = x^{n}m_{G}( − x ^{− 2})
and
 μ_{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:
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 Godsil (1981).
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 Zaslavsky (1981). The other is an integral identity due to Godsil (1981).
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 nonattacking 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) (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 #Pcomplete (Jerrum 1987). However, it can be computed more efficiently when additional structure about the graph is known. In particular, computing the matching polynomial on nvertex graphs of treewidth k is fixedparameter 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 cliquewidth k may be computed in time n^{O(k)} (Makowsky et al. 2006)
References
 Courcelle, B.; Makowsky, J. A.; Rotics, U. (2001), "On the fixed parameter complexity of graph enumeration problems definable in monadic secondorder logic", Discrete Applied Mathematics 108 (12): 23–52, doi:10.1016/S0166218X(00)002213, http://www.labri.fr/perso/courcell/CoursMaster/CMRDam.pdf.
 Farrell, E. J. (1980), "The matching polynomial and its relation to the acyclic polynomial of a graph", Ars Combinatoria 9: 221–228.
 Godsil, C.D. (1981), "Hermite polynomials and a duality relation for matchings polynomials", Combinatorica 1 (3): 257–262, doi:10.1007/BF02579331.
 Gutman, Ivan (1991), "Polynomials in graph theory", in Bonchev, D.; Rouvray, D. H., Chemical Graph Theory: Introduction and Fundamentals, Mathematical Chemistry, 1, Taylor & Francis, pp. 133–176, ISBN 9780856264542.
 Jerrum, Mark (1987), "Twodimensional monomerdimer systems are computationally intractable", Journal of Statistical Physics 48 (1): 121–134, doi:10.1007/BF01010403.
 Makowsky, J. A.; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Computing graph polynomials on graphs of bounded cliquewidth", Proc. 32nd International Workshop on GraphTheoretic Concepts in Computer Science (WG '06), Lecture Notes in Computer Science, 4271, SpringerVerlag, pp. 191–204, doi:10.1007/11917496_18, http://www.cs.technion.ac.il/~admlogic/TR/2006/WG06_makowsky.pdf.
 Riordan, John (1958), An Introduction to Combinatorial Analysis, New York: Wiley.
 Zaslavsky, Thomas (1981), "Complementary matching vectors and the uniform matching extension property", European Journal of Combinatorics 2: 91–103.
Categories:
Wikimedia Foundation. 2010.