Nothing Special   »   [go: up one dir, main page]

TOPICS
Search

Matching-Generating Polynomial


A k-matching in a graph G is a set of k edges, no two of which have a vertex in common (i.e., an independent edge set of size k). Let Phi_k be the number of k-matchings of the graph G, with Phi_0(G)=1 (since the empty set consisting of no edges is always a 0-matching) and Phi_1(G)=m the edge count of G. Then the matching-generating polynomial directly encodes the numbers of k-independent edge sets of a graph G and is defined by

 M(x)=sum_(k=0)^(nu(G))Phi_kx^k,
(1)

where nu(G) is the matching number of G.

The matching-generating polynomial is multiplicative with respect to disjoint unions of graphs, so for graphs G and H,

 M_(G union H union ...)(x)=M_G(x)M_H(x)...,,
(2)

where  union denotes a graph union.

The matching-generating polynomial M(x) is related to the matching polynomial mu(x) by

 mu(x)=x^nM(-x^(-2))
(3)

(Ellis-Monaghan and Merino 2008) and

 M(x)=(-i)^nx^(n/2)mu(ix^(-1/2)).
(4)

The matching-generating polynomial is closely related to the independence polynomial. In particular, since independent edge sets in the line graph L(G) correspond to independent vertex sets in the original graph G, the matching-generating polynomial of a graph G is equal to the independence polynomial of the line graph of G (Levit and Mandrescu 2005).

A graph G has a perfect matching iff

 |G|=2nu(G),
(5)

where |G|=n is the vertex count of G.

Precomputed matching-generating polynomials for many named graphs in terms of a variable x will be obtainable using GraphData[graph, "MatchingGeneratingPolynomial"][x].

The following table summarizes closed forms for the matching-generating polynomials of some common classes of graphs. Here, U(a,b,z) is a confluent hypergeometric function of the second kind, L_n(x) is a Laguerre polynomial, and L^^_n(x) is a Lucas polynomial.


See also

Independence Polynomial, Independent Edge Set, Matching, Matching Number, Matching Polynomial

Explore with Wolfram|Alpha

References

Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. http://arxiv.org/abs/0806.4699.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.

Cite this as:

Weisstein, Eric W. "Matching-Generating Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Matching-GeneratingPolynomial.html

Subject classifications