The matching-generating polynomial of a finite simple graph 
encodes the numbers of 
-matchings. A 
-matching 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 
.
The matching-generating polynomial is defined by
 |
(1)
|
where 
is the matching number of 
and 
is its vertex count.
The matching-generating polynomial is multiplicative with respect to disjoint graph unions, so for graphs 
and 
,
 |
(2)
|
where 
denotes a graph union.
For 
,
the matching-generating polynomial 
is related to the matching
polynomial 
by
 |
(3)
|
(Ellis-Monaghan and Merino 2008) and
 |
(4)
|
After expansion, both expressions give polynomials defined at 
.
The matching-generating polynomial is closely related to the independence polynomial. In particular, since matchings in a
graph 
correspond to independent
vertex sets in its line graph 
, the matching-generating polynomial of 
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].
For the ladder graph 
, the first three matching-generating polynomials
are
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
For 
,
the coefficients of 
in ascending powers of
give the corresponding rows of the triangle OEIS A046741.
Its 
row consists of 1, representing the empty 
array (Grimson 1974, p. 214).
The following table summarizes closed forms for the matching-generating polynomials of some common classes of graphs.
Here, 
is a positive integer, with 
for cycle graphs. The
star graph 
has 
vertices. The complete
graph expression is used for real 
. The remaining expressions involving 
or 
are used for 
. Each extends as a polynomial
to every 
. Also, 
is a confluent
hypergeometric function of the second kind, 
is a Laguerre polynomial,
and 
is a Lucas polynomial.
Arrays of Dumbbells." J. Math. Phys. 15,
214-216, 1974.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.Sloane, N. J. A.
Sequence