Combinatorica, An International Journal on Combinatorics and the Theory of Computing,
t. 24, p. 427-440, 2004.
Bodo Lass
Matching polynomials and duality
Abstract.
Let G be a simple graph on n vertices. An r-matching in
G is a set of r independent edges. The number of r-matchings
in G will be denoted by p(G,r). We set p(G,0) = 1 and
define the matching polynomial of G by
µ(G,x) := sum_{r} (-1)^r p(G,r) x^{n-2r}.
It is classical that the matching polynomial of a graph G determines the matching
polynomial of its complement G'. We make this statement more explicit by
proving new duality theorems by the generating function method for set functions.
In particular, we show that the matching functions exp[-x²/2]µ(G,x) and
exp[-x²/2]µ(G',x) are, up to a sign, real Fourier transforms of each other.
Moreover, we generalize Foata's combinatorial proof of the Mehler formula for Hermite polynomials
to matching polynomials. This provides a new short proof of the classical fact that
all zeros of µ(G,x) are real. The same statement is also proved for a common generalization
of the matching polynomial and the rook polynomial.
Les versions suivantes sont disponibles :
Version du journal :