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.

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

${\displaystyle m_{G}(x):=\sum _{k\geq 0}m_{k}x^{k}.}$

Another definition gives the matching polynomial as

${\displaystyle M_{G}(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}.}$

A third definition is the polynomial

${\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,

${\displaystyle M_{G}(x)=x^{n}m_{G}(-x^{-2})}$

and

${\displaystyle \mu _{G}(x,y)=y^{n}m_{G}(x/y^{2}).}$

The first type of matching polynomial is a direct generalization of the rook polynomial.

The second type of matching polynomial has remarkable connections with

${\displaystyle M_{K_{m,n}}(x)=n!L_{n}^{(m-n)}(x^{2}).\,}$

If G is the complete graph K_n, then M_G(x) is an Hermite polynomial:

${\displaystyle M_{K_{n}}(x)=H_{n}(x),\,}$

where H_n(x) is the "probabilist's Hermite polynomial" (1) in the definition of

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 non-attacking rook placements and rook polynomials.

The

The third type of matching polynomial was introduced by Farrell (1980) as a version of the "acyclic polynomial" used in chemistry.

On arbitrary graphs, or even

• 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.
• doi:10.1007/BF02579331
  .
• Gutman, Ivan (1991), "Polynomials in graph theory", in Bonchev, D.; Rouvray, D. H. (eds.), Chemical Graph Theory: Introduction and Fundamentals, Mathematical Chemistry, vol. 1, Taylor & Francis, pp. 133–176,
  ISBN 978-0-85626-454-2
  .
• 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) (PDF), Lecture Notes in Computer Science, vol. 4271, Springer-Verlag, pp. 191–204,
  ISBN 978-3-540-48381-6
  .
• 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,
  doi:10.1016/s0195-6698(81)80025-x
  .