The matching
polynomial of a
graph is based on the number of distinct
matchings (assuming the
nodes are
labeled) of the graph that have
k edges within them. Let
M(G,k) be the number of matchings containing
k edges. The simple form of the matching polynomial is:
MP(G) = Sum(i) M(G,i) w|V|-i
The traditional form of the matching polynomial is:
MP(G) = Sum(i) M(G,i) w1|V|-2*i w2i
Note M(G,k) = 0 if k > |V|/2.
Some examples:
- MP(Kj,k) = Sum(i<=j,i<=k) C(j,i) C(k,i) i! wj+k-2i
- MP(Kn) = Sum(i <= (n/2)) (C(n,2i) (2i)! / (i! 2i) wn - 2i
- MP(Pn) = w MP(Pn-1) + w MP(Pn-2)
Some basic properties:
- The w|V| term always has a coefficient of 1.
- The w|V|-1 term always has a coefficient of |E|, the number of edges.