- Source: Matching polynomial
In the mathematical fields of graph theory and combinatorics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function of the numbers of matchings of various sizes in a graph. It is one of several graph polynomials studied in algebraic graph theory.
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
m
G
(
x
)
:=
∑
k
≥
0
m
k
x
k
.
{\displaystyle m_{G}(x):=\sum _{k\geq 0}m_{k}x^{k}.}
Another definition gives the matching polynomial as
M
G
(
x
)
:=
∑
k
≥
0
(
−
1
)
k
m
k
x
n
−
2
k
.
{\displaystyle M_{G}(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}.}
A third definition is the polynomial
μ
G
(
x
,
y
)
:=
∑
k
≥
0
m
k
x
k
y
n
−
2
k
.
{\displaystyle \mu _{G}(x,y):=\sum _{k\geq 0}m_{k}x^{k}y^{n-2k}.}
Each type has its uses, and all are equivalent by simple transformations. For instance,
M
G
(
x
)
=
x
n
m
G
(
−
x
−
2
)
{\displaystyle M_{G}(x)=x^{n}m_{G}(-x^{-2})}
and
μ
G
(
x
,
y
)
=
y
n
m
G
(
x
/
y
2
)
.
{\displaystyle \mu _{G}(x,y)=y^{n}m_{G}(x/y^{2}).}
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 = 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:
M
K
m
,
n
(
x
)
=
n
!
L
n
(
m
−
n
)
(
x
2
)
.
{\displaystyle M_{K_{m,n}}(x)=n!L_{n}^{(m-n)}(x^{2}).\,}
If G is the complete graph Kn, then MG(x) is an Hermite polynomial:
M
K
n
(
x
)
=
H
n
(
x
)
,
{\displaystyle M_{K_{n}}(x)=H_{n}(x),\,}
where Hn(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 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 Zaslavsky (1981). The other is an integral identity due to Godsil (1981).
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 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 mG(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 nO(k) (Makowsky et al. 2006).
References
Courcelle, B.; Makowsky, J. A.; Rotics, U. (2001), "On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic" (PDF), Discrete Applied Mathematics, 108 (1–2): 23–52, doi:10.1016/S0166-218X(00)00221-3.
Farrell, E. J. (1980), "The matching polynomial and its relation to the acyclic polynomial of a graph", Ars Combinatoria, 9: 221–228.
Godsil, C.D. (1981), "Hermite polynomials and a duality relation for matchings polynomials", Combinatorica, 1 (3): 257–262, doi:10.1007/BF02579331.
Gutman, Ivan (1991), "Polynomials in graph theory", in Bonchev, D.; Rouvray, D. H. (eds.), Chemical Graph Theory: Introduction and Fundamentals, Mathematical Chemistry, vol. 1, Taylor & Francis, pp. 133–176, ISBN 978-0-85626-454-2.
Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable", Journal of Statistical Physics, 48 (1): 121–134, Bibcode:1987JSP....48..121J, doi:10.1007/BF01010403.
Makowsky, J. A.; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Computing graph polynomials on graphs of bounded clique-width", Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06) (PDF), Lecture Notes in Computer Science, vol. 4271, Springer-Verlag, pp. 191–204, doi:10.1007/11917496_18, ISBN 978-3-540-48381-6.
Riordan, John (1958), An Introduction to Combinatorial Analysis, New York: Wiley.
Zaslavsky, Thomas (1981), "Complementary matching vectors and the uniform matching extension property", European Journal of Combinatorics, 2: 91–103, doi:10.1016/s0195-6698(81)80025-x.
Kata Kunci Pencarian:
- Matching polynomial
- Matching (graph theory)
- Rook polynomial
- Perfect matching
- Chebyshev polynomials
- Graph polynomial
- 3-dimensional matching
- Hermite polynomials
- Schwartz–Zippel lemma
- Time complexity
