Matching polynomial

Short description: Graph polynomial generating numbers of matchings

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

[math]\displaystyle{ m_G(x) := \sum_{k\geq0} m_k x^k. }[/math]

Another definition gives the matching polynomial as

[math]\displaystyle{ M_G(x) := \sum_{k\geq0} (-1)^k m_k x^{n-2k}. }[/math]

A third definition is the polynomial

[math]\displaystyle{ \mu_G(x,y) := \sum_{k\geq0} m_k x^k y^{n-2k}. }[/math]

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

[math]\displaystyle{ M_G(x) = x^n m_G(-x^{-2}) }[/math]

and

[math]\displaystyle{ \mu_G(x,y) = y^n m_G(x/y^2). }[/math]

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:

[math]\displaystyle{ M_{K_{m,n}}(x) = n! L_n^{(m-n)}(x^2). \, }[/math]

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

[math]\displaystyle{ M_{K_n}(x) = H_n(x), \, }[/math]

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 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 (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.

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 #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). The matching polynomial of a graph with n vertices and clique-width k may be computed in time n^O(k) (Makowsky Rotics).

References

• "On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic", Discrete Applied Mathematics 108 (1-2): 23–52, 2001, doi:10.1016/S0166-218X(00)00221-3, http://www.labri.fr/perso/courcell/CoursMaster/CMR-Dam.pdf .
• Farrell, E. J. (1980), "The matching polynomial and its relation to the acyclic polynomial of a graph", Ars Combinatoria 9: 221–228 .
• "Hermite polynomials and a duality relation for matchings polynomials", Combinatorica 1 (3): 257–262, 1981, 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 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), Lecture Notes in Computer Science, 4271, Springer-Verlag, pp. 191–204, doi:10.1007/11917496_18, https://www.cs.technion.ac.il/~admlogic/TR/2006/WG06_makowsky.pdf .
• An Introduction to Combinatorial Analysis, New York: Wiley, 1958 .
• 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 .