# Matching polynomial

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.

## 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) := \sum_{k\geq0} m_k x^k.$

Another definition gives the matching polynomial as

$M_G(x) := \sum_{k\geq0} (-1)^k m_k x^{n-2k}.$

A third definition is the polynomial

$\mu_G(x,y) := \sum_{k\geq0} m_k x^k y^{n-2k}.$

Each type has its uses, and all are equivalent by simple transformations. For instance,

MG(x) = xnmG( − x − 2)

and

μG(x,y) = ynmG(x / y2).

## 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). \,$

If G is the complete graph Kn, then MG(x) is an Hermite polynomial:

$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 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)

## References

• Courcelle, B.; Makowsky, J. A.; Rotics, U. (2001), "On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic", Discrete Applied Mathematics 108 (1-2): 23–52, doi:10.1016/S0166-218X(00)00221-3 .
• 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), "Two-dimensional monomer-dimer 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 clique-width", Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06), Lecture Notes in Computer Science, 4271, Springer-Verlag, pp. 191–204, doi:10.1007/11917496_18 .
• 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 .

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

• Schwartz-Zippel lemma and testing polynomial identities — Polynomial identity testing is the problem of determining whether a given multivariate polynomial is the0 polynomial or identically equal to 0. The input to the problem is an n variable polynomial over a fieldF. It can occur in the following… …   Wikipedia

• Tutte polynomial — This article is about the Tutte polynomial of a graph. For the Tutte polynomial of a matroid, see Matroid. The polynomial x4 + x3 + x2y is the Tutte polynomial of the Bull graph. The red line shows the intersection with the plane …   Wikipedia

• Chromatic polynomial — All nonisomorphic graphs on 3 vertices and their chromatic polynomials, clockwise from the top. The independent 3 set: k3. An edge and a single vertex: k2(k − 1). The 3 path: k(k − 1)2. The 3 clique …   Wikipedia

• Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

• List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

• Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

• Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

• Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

• Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia