# Matching polynomial of a graph

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 05C70 Secondary: 05C31 [MSN][ZBL]

A matching cover (or simply a matching) in a graph \$G\$ is taken to be a subgraph of \$G\$ consisting of disjoint (independent) edges of \$G\$, together with the remaining nodes of \$G\$ as (isolated) components. A matching is called a \$k\$-matching if it contains exactly \$k\$ edges. If \$G\$ contains \$p\$ nodes, then the extreme cases are:

i) \$p\$ is even and \$k=p/2\$; in this case, all the nodes of \$G\$ are covered with edges (a perfect matching); and

ii) \$k=0\$; in this case, none of the nodes of \$G\$ are covered by edges (the empty matching).

If a matching contains \$k\$ edges, then it will have \$p-2k\$ component nodes. Now assign weights (or indeterminates over the complex numbers) \$w_1\$ and \$w_2\$ to each node and edge of \$G\$, respectively. Take the weight of a matching to be the product of the weights of all its components. Then the weight of a \$k\$-matching will be \$w_1^{p-2k}w_2^k\$. The matching polynomial of \$G\$, denoted by \$M(G;w)\$, is the sum of the weights of all the matchings in \$G\$. Setting \$w_1=w_2=w\$, then the resulting polynomial is called the simple matching polynomial of \$G\$.

The matching polynomial was introduced in [a1]. Basic algorithms for finding matching polynomials of arbitrary graphs, basic properties of the polynomial, and explicit formulas for the matching polynomials of many well-known families of graphs are given in [a1]. The coefficients of the polynomial have been investigated [a8]. The analytical properties of the polynomial have also been investigated [a10].

Various polynomials used in statistical physics and in chemical thermodynamics can be shown to be matching polynomials. The matching polynomial is related to many of the well-known classical polynomials encountered in combinatorics. These include the Chebyshev polynomials, the Hermite polynomials and the Laguerre polynomials. An account of these and other connections can be found in [a14], [a16]. The classical rook polynomial is also a special matching polynomial; and in fact, rook theory can be developed entirely through matching polynomials (see [a4], [a5]). The matching polynomial is also related to various other polynomials encountered in graph theory. These include the chromatic polynomial (see [a13]), the characteristic polynomial and the acyclic polynomial (see [a15] and [a3]). The matching polynomial itself is one of a general class of graph polynomials, called F-polynomials (see [a2]). Two graphs are called co-matching if and only if they have the same matching polynomial. A graph is called matching unique if and only if no other graph has the same matching polynomial. Co-matching graphs and matching unique graphs have been investigated (see [a6], [a9]). It has been shown that the matching polynomial of certain graphs (called D-graphs) can be written as determinants of matrices. It appears that for every graph there exists a co-matching D-graph. The construction of co-matching D-graphs is one the main subjects of current interest in the area (see [a7], [a11], [a12]).

#### References

 [a1] E.J. Farrell, "Introduction to matching polynomials" J. Combin. Th. B , 27 (1979) pp. 75–86 [a2] E.J. Farrell, "On a general class of graph polynomials" J. Combin. Th. B , 26 (1979) pp. 111–122 [a3] E.J. Farrell, "The matching polynomial and its relation to the acyclic polynomial of a graph" Ars Combinatoria , 9 (1980) pp. 221–228 [a4] E.J. Farrell, "The matching polynomial and its relation to the Rook polynomial" J. Franklin Inst. , 325 : 4 (1988) pp. 527–536 [a5] E.J. Farrell, "A graph-theoretic approach to Rook theory" Caribb. J. Math. , 7 (1988) pp. 1–47 [a6] E.J. Farrell, J.M. Guo, "On the characterizing properties of the matching polynomial" Vishwa Internat. J. Graph Th. , 2 : 1 (1993) pp. 55–62 [a7] E.J. Farrell, S.A. Wahid, "Matching polynomials: A matrix approach and its applications" J. Franklin Inst. , 322 (1986) pp. 13–21 [a8] E.J. Farrell, J.M. Guo, G.M. Constantine, "On the matching coefficients" Discr. Math. , 89 (1991) pp. 203–210 [a9] E.J. Farrell, S.A. Wahid, "Some general classes of comatching graphs" Internat. J. Math. Math. Sci. , I0 : 3 (1987) pp. 519–524 [a10] E.J. Farrell, S.A. Wahid, "Some analytical properties of the matching polynomial of a graph" , Proc. Fifth Caribb. Conf. in Comb. and Graph Th., Jan.5-8, 1988 pp. 105–119 [a11] E.J. Farrell, S.A. Wahid, "D-graphs I: An introduction to graphs whose matching polynomials are determinants of matrices" Bull. ICA , 15 (1995) pp. 81–86 [a12] E.J. Farrell, S.A. Wahid, "D-graphs II: Constructions of D-graphs for some families of graphs with even cycles" Utilitas Math. , 56 (1999) pp. 167–176 [a13] E.J. Farrell, E.G. Whitehead, "Connections between the matching and chromatic polynomials" Internat. J. Math. Math. Sci. , 15 : 4 (1992) pp. 757–766 [a14] I. Gutman, "The matching polynomial" MATCH : 6 (1979) pp. 75–91 [a15] I. Gutman, "The acyclic polynomial of a graph" Publ. Inst. Math. Beograd , 22 (36) (1977) pp. 63–69 [a16] C.D. Godsil, I. Gutman, "On the theory of the matching polynomial" J. Graph Th. , 5 (1981) pp. 137–145
How to Cite This Entry:
Matching polynomial of a graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matching_polynomial_of_a_graph&oldid=52600
This article was adapted from an original article by E.J. Farrell (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article