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.
