display | more...
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.

Log in or register to write something here or to contact authors.