The matching polynomial
of a graph
is based on the number of distinct matching
s (assuming the nodes
) 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.
- 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.