Matching Polynomial

A -matching in a graph  is a set of  edges, no two of which have a vertex in common (i.e., an independent edge set of size ). Let  be the number of -matchings in the graph , with  and  the number of edges of . Then the matching polynomial is defined by

(1)

where  vertex count of  (Ivanciuc and Balaban 2000, p. 92; Levit and Mandrescu 2005) and  is the matching number (which satisfies , where  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  and is defined by

(2)

but  is firmly established. Fortunately, the two are related by

(3)

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

(4)

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

The matching polynomial has a nonzero  coefficient (or equivalently, the matching-generating polynomial is of degree  for a graph on  nodes) iff the graph has a perfect matching.

Precomputed matching polynomials for many named graphs in terms of a variable  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,  is a modified Hermite polynomial,  is the usual Hermite polynomial,  is a Laguerre polynomial,  is a confluent hypergeometric function of the second kind,  is a Lucas polynomial, , , and .

graph
book graph
centipede graph
complete graph
complete bipartite graph
cycle graph
empty graph
gear graph
helm graph
ladder rung graph
pan graph
path graph
star graph
sunlet graph
wheel graph

The following table summarizes the recurrence relations for independence polynomials for some simple classes of graphs.

antiprism graph	4
book graph	3
centipede graph	2
-crossed prism graph	3
cycle graph	2
gear graph	4
helm graph	4
ladder graph	3
ladder rung graph	1
Möbius ladder	4
pan graph	2
path graph	2
prism graph	4
star graph	2
sunlet graph	2
web graph	4
wheel graph	4

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

	matching polynomial	graphs
4		claw graph,
5		banner graph, 3-centipede graph
5		-fan graph, -lollipop graph
5		butterfly graph, kite graph
5		,
5		, path graph
5		house graph, complete bipartite graph
5		cricket graph,
5		fork graph,

For any graph , the matching polynomial  has only real zeros.

REFERENCES

Aihara, J. "A New Definition of Dewar-Type Resonance Energies." J. Amer. Chem. Soc. 98, 2750-2758, 1976.

Devillers, J. and A. T. Balaban (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."