# Matching polynomial of a graph

2010 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]).

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=43169
This article was adapted from an original article by E.J. Farrell (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article