TOPICS

# Matching-Generating Polynomial

A -matching in a graph is a set of edges, no two of which have a vertex in common (i.e., an independent edge set of size ). Let be the number of -matchings of the graph , with (since the empty set consisting of no edges is always a 0-matching) and the edge count of . Then the matching-generating polynomial directly encodes the numbers of -independent edge sets of a graph and is defined by

 (1)

where is the matching number of .

The matching-generating polynomial is multiplicative with respect to disjoint unions of graphs, so for graphs and ,

 (2)

where denotes a graph union.

The matching-generating polynomial is related to the matching polynomial by

 (3)

(Ellis-Monaghan and Merino 2008) and

 (4)

The matching-generating polynomial is closely related to the independence polynomial. In particular, since independent edge sets in the line graph correspond to independent vertex sets in the original graph , the matching-generating polynomial of a graph is equal to the independence polynomial of the line graph of (Levit and Mandrescu 2005).

A graph has a perfect matching iff

 (5)

where is the vertex count of .

Precomputed matching-generating polynomials for many named graphs in terms of a variable will be obtainable using GraphData[graph, "MatchingGeneratingPolynomial"][x].

The following table summarizes closed forms for the matching-generating polynomials of some common classes of graphs. Here, is a confluent hypergeometric function of the second kind, is a Laguerre polynomial, and is a Lucas polynomial.

Independence Polynomial, Independent Edge Set, Matching, Matching Number, Matching Polynomial

## Explore with Wolfram|Alpha

More things to try:

## References

Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. http://arxiv.org/abs/0806.4699.Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 (Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.

## Cite this as:

Weisstein, Eric W. "Matching-Generating Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Matching-GeneratingPolynomial.html