Matching polynomial · Lablypedia

Related on Lably

Through Mathematics, Combinatorics and Chemistry

LabHide & Seek Ghar LabTarazu Bazaar LabThe Counting Market LabFestival Mela

Definition

Several different types of matching polynomials have been defined. Let G be a graph with n vertices and let m_k be the number of k-edge matchings.

One matching polynomial of G is $m_{G} (x) := \sum_{k \geq 0} m_{k} x^{k} .$

Another definition gives the matching polynomial as $M_{G} (x) := \sum_{k \geq 0} (- 1)^{k} m_{k} x^{n - 2 k} .$

A third definition is the polynomial $μ_{G} (x, y) := \sum_{k \geq 0} m_{k} x^{k} y^{n - 2 k} .$

Each type has its uses, and all are equivalent by simple transformations. For instance, $M_{G} (x) = x^{n} m_{G} (- x^{- 2})$ and $μ_{G} (x, y) = y^{n} m_{G} (x / y^{2}) .$

4 more chapters are free with a Lably account.

Connections to other polynomials

The first type of matching polynomial is a direct generalization of the rook polynomial.

The second type of matching polynomial has remarkable connections with orthogonal polynomials. For instance, if G = K_m,n, the complete bipartite graph, then the second type of matching polynomial is related to the generalized Laguerre polynomial L_n^α(x) by the identity:

$M_{K_{m, n}} (x) = n! L_{n}^{(m - n)} (x^{2}) .$

If G is the complete graph K_n, then M_G(x) is an Hermite polynomial: $M_{K_{n}} (x) = H_{n} (x),$ where H_n(x) is the "probabilist's Hermite polynomial" (1) in the definition of Hermite polynomials. These facts were observed by Godsil (1981).

If G is a forest, then its matching polynomial is equal to the characteristic polynomial of its adjacency matrix.

If G is a path or a cycle, then M_G(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 Zaslavsky (1981). The other is an integral identity due to Godsil (1981).

There is a similar relation for a subgraph G of K_m,n and its complement in K_m,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 index 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 m_G(1) (Gutman 1991).

The third type of matching polynomial was introduced by Farrell (1980) as a version of the "acyclic polynomial" used in chemistry.

Computational complexity

On arbitrary graphs, or even planar graphs, computing the matching polynomial is #P-complete (Jerrum 1987). 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 (Courcelle, Makowsky & Rotics 2001). The matching polynomial of a graph with n vertices and clique-width k may be computed in time n^O(k) (Makowsky et al. 2006).

More in Discrete mathematics

SubsetSet whose elements all belong to another set Graph (discrete mathematics)Vertices connected in pairs by edges Set theoryBranch of mathematics that studies sets AxiomStatement that is taken to be true Graph theoryArea of discrete mathematics First-order logicType of logical system