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.

graph
complete graph
complete bipartite graph
cycle graph
empty graph
star graph

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.