J. Combin. Theory Ser. B, t. 102, p. 411-423, 2012.
Bodo Lass
Mehler Formulae for Matching Polynomials of Graphs and Independence Polynomials of Clawfree Graphs
Abstract.
The independence polynomial of a graph G is the polynomial
sum_I x^|I|, summed over all independent subsets of V(G).
We show that if G is clawfree, then there exists a Mehler formula for
its independence polynomial. This was proved for matching polynomials
in
Matching polynomials and duality
and extends the combinatorial proof of the Mehler formula found by
Foata.
It implies immediately that all the roots of the independence polynomial
of a clawfree graph are real, answering a question posed by
Hamidoune
and
Stanley
and solved by
Chudnovsky and Seymour.
We also prove a Mehler formula for the multivariate matching polynomial, extending results of
Matching polynomials and duality.
Les versions suivantes sont disponibles :
Version du journal :