TOPICS
Search

Matching Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The matching polynomial of a graph G is defined by

mu(x)=sum_(k=0)^(nu(G))(-1)^kPhi_kx^(n-2k),
(1)

where Phi_k counts the k-matchings (independent edge sets of size k), n=|G| is the vertex count, and nu(G) is the matching number (Ivanciuc and Balaban 2000, p. 92; Levit and Mandrescu 2005). In particular, Phi_0=1 and Phi_1=m, where m is the edge count. The matching number satisfies nu(G)<=|_n/2_|, where |_x_| is the floor function.

The matching polynomial is also known as the acyclic polynomial (Gutman and Trinajstić 1976, Devillers and Balaban 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 G and is defined by

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

but mu(x) is firmly established. Fortunately, the two are related by

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

(Ellis-Monaghan and Merino 2008; typo corrected), so

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

The notation mu(x) for the matching polynomial is unrelated to the mu(G) used for the mutual-visibility number, the mu used for circuit rank, and the mu parameter of a strongly regular graph.

The matching polynomial is closely related to the independence polynomial. In particular, the matching-generating polynomial of a graph G is equal to the independence polynomial of the line graph of G (Levit and Mandrescu 2005).

The matching polynomial has a nonzero constant coefficient a_0 (or equivalently, the matching-generating polynomial is of polynomial degree n/2 for a graph on an even number n of nodes) iff the graph has a perfect matching.

Precomputed matching polynomials for many named graphs in terms of a variable x 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, He_n(x) is a modified Hermite polynomial, H_n(x) is the usual Hermite polynomial, L_n(x) is a Laguerre polynomial, U(a,b,z) is a confluent hypergeometric function of the second kind, L^^_n(x) is a Lucas polynomial, s=sqrt(1-6x^2+x^4), t=sqrt(x^2-4), and v=sqrt(1-6x^2+x^4).

graphmu(x)
book graph S_(n+1) square P_2(x-1)^(n-2)(x+1)^(n-2)[n^2x^2+(x^2-1)^3+n(-1+2x^2-2x^4)]
centipede graph((-1+v+x^2)^(n+1)-(-1-v+x^2)^(n+1))/(2^(n+1)v)
complete graph K_nHe_n(x)
=2^(-n/2)H_n(x/(sqrt(2)))
complete bipartite graph K_(n,n)(-1)^nn!L_n(x^2)
=U(-n,1,x^2)
cycle graph C_ni^nL^^_n(-ix)
empty graph K^__nx^n
gear graph((n+tx)(-2-tx+x^2)^n+(-n+tx)(-2+tx+x^2)^n)/(2^nt)
helm graph((n+s)x(-1-s+x^2)^n-(n-s)x(-1+s+x^2)^n)/(2^ns)
ladder rung graph nP_2(x-1)^n(x+1)^n
pan graph((x+t)^n(tx-1)+(x-t)^n(tx+1))/(2^nt)
path graph P_n((x+t)^(n+1)-(x-t)^(n+1))/(2^(n+1)t)
star graph S_nx^(n-2)(x^2-n+1)
sunlet graph C_n circledot K_12^(-n)((-1+x^2-sqrt(1-6x^2+x^4))^n+(-1+x^2+sqrt(1-6x^2+x^4))^n)
wheel graph W_n(x(n+x^2-5)[(x-t)^n-(t+x)^n]+t(n+x^2-1)[(x-t)^n+(t+x)^n])/(2^(n+1)t)

The following table summarizes recurrence relations for matching polynomials of some classes of graphs, with p_n(x)=mu(G_n,x). The antiprism recurrence applies for n>=7, and the book-graph recurrence applies for n>=5.

graphorderrecurrence
antiprism graph4p_n(x)=(x^2-2)p_(n-1)(x)-(2x^2-1)p_(n-2)(x)+(x^2+2)p_(n-3)(x)-p_(n-4)(x)
book graph S_(n+1) square P_23p_n(x)=3(x^2-1)p_(n-1)(x)-3(x^2-1)^2p_(n-2)(x)+(x^2-1)^3p_(n-3)(x)
centipede graph2p_n(x)=(x-1)(x+1)p_(n-1)(x)-x^2p_(n-2)(x)
(2n)-crossed prism graph3p_n(x)=-2(x^2-2)^2p_(n-2)(x)+(x-1)(x+1)(x^2-5)p_(n-1)(x)+4p_(n-3)(x)
cycle graph C_n2p_n(x)=xp_(n-1)(x)-p_(n-2)(x)
gear graph4p_n(x)=2(x^2-2)p_(n-1)(x)-(x^4-4x^2+6)p_(n-2)(x)+2(x^2-2)p_(n-3)(x)-p_(n-4)(x)
helm graph4p_n(x)=2(x-1)(x+1)p_(n-1)(x)-(x^4+1)p_(n-2)(x)+2(x-1)(x+1)x^2p_(n-3)(x)-x^4p_(n-4)(x)
ladder graph P_2 square P_n3p_n(x)=(-2+x^2)p_(n-1)(x)-x^2p_(n-2)(x)+p_(n-3)(x)
ladder rung graph nP_21p_n(x)=(x-1)(x+1)p_(n-1)(x)
Möbius ladder M_n4p_n(x)=(x^2-1)p_(n-1)(x)+2(1-x^2)p_(n-2)(x)+(x^2+1)p_(n-3)(x)-p_(n-4)(x)
pan graph2p_n(x)=xp_(n-1)(x)-p_(n-2)(x)
path graph P_n2p_n(x)=xp_(n-1)(x)-p_(n-2)(x)
prism graph4p_n(x)=(x^2-1)p_(n-1)(x)+2(1-x^2)p_(n-2)(x)+(x^2+1)p_(n-3)(x)-p_(n-4)(x)
star graph S_n2p_n(x)=2xp_(n-1)(x)-x^2p_(n-2)(x)
sunlet graph C_n circledot K_12p_n(x)=(x+1)(x-1)p_(n-1)(x)-x^2p_(n-2)(x)
web graph4p_n(x)=x^5p_(n-3)(x)-x^4p_(n-4)(x)+(x^2-2)xp_(n-1)(x)-(2x^4-4x^2+1)p_(n-2)(x)
wheel graph W_n4p_n(x)=2xp_(n-1)(x)-(x^2+2)p_(n-2)(x)+2xp_(n-3)(x)-p_(n-4)(x)

Nonisomorphic graphs do not necessarily have distinct matching polynomials. The following table summarizes some co-matching graphs.

nmatching polynomialgraphs
4x^2(-3+x^2)claw graph, (4,6)
5(-1+x)x(1+x)(-6+x^2)(3,2)-fan graph, (4,1)-lollipop graph
5(-1+x)x(1+x)(-5+x^2)butterfly graph, kite graph
5x^3(-3+x^2)(5,4), (5,8)
5(-1+x)x(1+x)(-3+x^2)(5,20), path graph P_5
5x(6-6x^2+x^4)house graph, complete bipartite graph K_(2,3)
5x(2-5x^2+x^4)cricket graph, (5,15)
5x(2-4x^2+x^4)fork graph, (5,14)

The banner graph has matching polynomial x(x^2-1)(x^2-4). The 3-centipede graph has six vertices and matching polynomial (x^2-1)(x^4-4x^2+1), so these graphs are not co-matching.

For any graph G, the matching polynomial mu(x) has only real roots.

See also

Acyclic Polynomial, Characteristic Polynomial, Hosoya Index, Independent Edge Set, Matching, Matching-Generating Polynomial, Matching Number, Perfect Matching

Explore with Wolfram|Alpha

References

Aihara, J. "A New Definition of Dewar-Type Resonance Energies." J. Amer. Chem. Soc. 98, 2750-2758, 1976.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 92-94, 2000.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. https://arxiv.org/abs/0806.4699.Godsil, C. D. Algebraic Combinatorics. Chapman and Hall, 1993.Godsil, C. D. and Gutman, I. "On the Theory of the Matching Polynomial." J. Graph Th. 5, 137-144, 1981. https://doi.org/10.1002/jgt.3190050203.Gutman, I. "Polynomials in Graph Theory." In Chemical Graph Theory: Introduction and Fundamentals (Ed. D. Bonchev and D. H. Rouvray). New York: Abacus Press, 1991.Gutman, I. and Trinajstić, N. "Graph Theory and Molecular Orbitals, XIV. On Topological Definition of Resonance Energy." Acta Chimica Academiae Scientiarum Hungaricae 91, 203-209, 1976.Ivanciuc, O. and Balaban, A. T. "The Graph Description of Chemical Structures." Ch. 3 in Topological Indices and Related Descriptors in QSAR and QSPR (Ed. J. Devillers and A. T. Balaban). Amsterdam, Netherlands: Gordon and Breach, pp. 59-167, 2000.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.Lovász, L. and Plummer, M. D. Matching Theory. Amsterdam, Netherlands: North-Holland, 1986.Lundow, P. H. "Enumeration of Matchings in Polygraphs." Department of Mathematics, Umea University. Research report. 1998. http://www.theophys.kth.se/~phl/Text/1factors2.ps.gz. Lundow, P. H. "GrafPack." http://www.theophys.kth.se/~phl/Mathematica/.Sloane, N. J. A. Sequences A046741 and A096713 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Matching Polynomial

Cite this as:

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

Subject classifications