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 in the graph , with and the number of edges of . Then the matching polynomial is defined by
where vertex count of (Ivanciuc and Balaban 2000, p. 92; Levit and Mandrescu 2005) and is the matching number (which satisfies , where is the floor function).
The matching polynomial is also known as the acyclic polynomial (Gutman and Trinajstić 1976, Devillers and Merino 2000), matching defect polynomial (Lovász and Plummer 1986), and reference polynomial (Aihara 1976).
A more natural polynomial might be the matching-generating polynomial which directly encodes the numbers of independent edge sets of a graph and is defined by
but is firmly established. Fortunately, the two are related by
(Ellis-Monaghan and Merino 2008; typo corrected), so
The matching polynomial is closely related to the independence polynomial. In particular, the matching-generating polynomial of a graph is equal to the independence polynomial of the line graph of (Levit and Mandrescu 2005).
The matching polynomial has a nonzero coefficient (or equivalently, the matching-generating polynomial is of degree for a graph on nodes) iff the graph has a perfect matching.
Precomputed matching polynomials for many named graphs in terms of a variable can be obtained using GraphData[graph, "MatchingPolynomial"][x].
The following table summarizes closed forms for the matching polynomials of some common classes of graphs. Here, is a modified Hermite polynomial, is the usual Hermite polynomial, is a Laguerre polynomial, is a confluent hypergeometric function of the second kind, is a Lucas polynomial, , , and .
|book graph |
|complete graph |
|complete bipartite graph |
|cycle graph |
|empty graph |
|ladder rung graph |
|path graph |
|star graph |
|sunlet graph |
|wheel graph |
The following table summarizes the recurrence relations for independence polynomials for some simple classes of graphs.
|book graph ||3|
|-crossed prism graph||3|
|cycle graph ||2|
|ladder graph ||3|
|ladder rung graph ||1|
|Möbius ladder ||4|
|path graph ||2|
|star graph ||2|
|sunlet graph ||2|
|wheel graph ||4|
Nonisomorphic graphs do not necessarily have distinct matching polynomials. The following table summarizes some co-matching graphs.
|4||claw graph, |
|5||banner graph, 3-centipede graph|
|5||-fan graph, -lollipop graph|
|5||butterfly graph, kite graph|
|5||, path graph |
|5||house graph, complete bipartite graph |
|5||cricket graph, |
|5||fork graph, |
For any graph , the matching polynomial has only real zeros.