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

Matching Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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 in the graph G, with Phi_0(G)=1 and Phi_1(G)=m the number of edges of G. Then the matching polynomial is defined by

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

where n=|G| vertex count of G (Ivanciuc and Balaban 2000, p. 92; Levit and Mandrescu 2005) and nu(G) is the matching number (which 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 Merino 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 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 a_0 coefficient (or equivalently, the matching-generating polynomial is of degree n for a graph on n 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 u=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 the recurrence relations for independence polynomials for some simple classes of graphs.

antiprism graph4p_n(x)=(x-2)^2p_(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)=3p_(n-1)(x)-3p_(n-2)(x)+p_(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(-2+x)(-1+x)x(1+x)(2+x)banner graph, 3-centipede graph
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)

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

See also

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. http://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 Theory 5, 137-144, 2006.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 Web Resource. https://mathworld.wolfram.com/MatchingPolynomial.html

Subject classifications