Matching polynomial
Encyclopedia
In graph theory
and combinatorics
, both fields within mathematics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function
of the numbers of matchings of various sizes in a graph.
One matching polynomial of G is
Another definition gives the matching polynomial as
A third definition is the polynomial
Each type has its uses, and all are equivalent by simple transformations. For instance,
and
.
The second type of matching polynomial has remarkable connections with orthogonal polynomials
. For instance, if G = Km,n, the complete bipartite graph
, then the second type of matching polynomial is related to the generalized Laguerre polynomial Lnα(x) by the identity:
If G is the complete graph
Kn, then MG(x) is an Hermite polynomial:
where Hn(x) is the "probabilist's Hermite polynomial" (1) in the definition of Hermite polynomials. These facts were observed by .
If G is a path
or a cycle
, then MG(x) is a Chebyshev polynomial. In this case
μG(1,x) is a Fibonacci polynomial or Lucas polynomial respectively.
There is a similar relation for a subgraph G of Km,n and its complement in Km,n. This relation, due to Riordan (1958), was known in the context of non-attacking rook placements and rook polynomials.
of a graph G, its number of matchings, is used in chemoinformatics as a structural descriptor of a molecular graph. It may be evaluated as mG(1) .
The third type of matching polynomial was introduced by as a version of the "acyclic polynomial" used in chemistry
.
s, computing the matching polynomial is #P-complete . However, it can be computed more efficiently when additional structure about the graph is known. In particular,
computing the matching polynomial on n-vertex graphs of treewidth k is fixed-parameter tractable: there exists an algorithm whose running time, for any fixed constant k, is a polynomial in n with an exponent that does not depend on k .
The matching polynomial of a graph with n vertices and clique-width
k may be computed in time nO(k)
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, both fields within mathematics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function
Generating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
of the numbers of matchings of various sizes in a graph.
Definition
Several different types of matching polynomials have been defined. Let G be a graph with n vertices and let mk be the number of k-edge matchings.One matching polynomial of G is
Another definition gives the matching polynomial as
A third definition is the polynomial
Each type has its uses, and all are equivalent by simple transformations. For instance,
and
Connections to other polynomials
The first type of matching polynomial is a direct generalization of the rook polynomialRook polynomial
In combinatorial mathematics, a rook polynomial is a generating polynomial of the number of ways to place non-attacking rooks on a board that looks like a checkerboard; that is, no two rooks may be in the same row or column...
.
The second type of matching polynomial has remarkable connections with orthogonal polynomials
Orthogonal polynomials
In mathematics, the classical orthogonal polynomials are the most widely used orthogonal polynomials, and consist of the Hermite polynomials, the Laguerre polynomials, the Jacobi polynomials together with their special cases the ultraspherical polynomials, the Chebyshev polynomials, and the...
. For instance, if G = Km,n, the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
, then the second type of matching polynomial is related to the generalized Laguerre polynomial Lnα(x) by the identity:
If G is the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
Kn, then MG(x) is an Hermite polynomial:
where Hn(x) is the "probabilist's Hermite polynomial" (1) in the definition of Hermite polynomials. These facts were observed by .
If G is a path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
or a cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
, then MG(x) is a Chebyshev polynomial. In this case
μG(1,x) is a Fibonacci polynomial or Lucas polynomial respectively.
Complementation
The matching polynomial of a graph G with n vertices is related to that of its complement by a pair of (equivalent) formulas. One of them is a simple combinatorial identity due to . The other is an integral identity due to .There is a similar relation for a subgraph G of Km,n and its complement in Km,n. This relation, due to Riordan (1958), was known in the context of non-attacking rook placements and rook polynomials.
Applications in chemical informatics
The Hosoya indexHosoya index
The Hosoya index, also known as the Z index, of a graph is the total number of matchings in it. The Hosoya index is always at least one, because the empty set of edges is counted as a matching for this purpose. Equivalently, the Hosoya index is the number of non-empty matchings plus...
of a graph G, its number of matchings, is used in chemoinformatics as a structural descriptor of a molecular graph. It may be evaluated as mG(1) .
The third type of matching polynomial was introduced by as a version of the "acyclic polynomial" used in chemistry
Chemistry
Chemistry is the science of matter, especially its chemical reactions, but also its composition, structure and properties. Chemistry is concerned with atoms and their interactions with other atoms, and particularly with the properties of chemical bonds....
.
Computational complexity
On arbitrary graphs, or even planar graphPlanar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s, computing the matching polynomial is #P-complete . However, it can be computed more efficiently when additional structure about the graph is known. In particular,
computing the matching polynomial on n-vertex graphs of treewidth k is fixed-parameter tractable: there exists an algorithm whose running time, for any fixed constant k, is a polynomial in n with an exponent that does not depend on k .
The matching polynomial of a graph with n vertices and clique-width
Clique-width
In graph theory, the clique-width of a graph G is the minimum number of labels needed to construct G by means of the following 4 operations :#Creation of a new vertex v with label i...
k may be computed in time nO(k)