no. 16 · Tuesday 17 November 2026
Duality Relations of Graph Polynomials
Abstract
The duality theorem of Lass relates the matching polynomials of a simple graph $G$ with the matching polynomials of its complement $\bar G$. In particular, this relation gives rise to Godsil's result, which offers a nice interpretation of the Lebesgue integral associated with the Hermite orthogonality measure. In this work, we show that similar to matching polynomials, the path-cover polynomials also satisfy duality relations and give combinatorial interpretations of the Lebesgue integral and the inner product in the space of associated Laguerre polynomials. Similar duality relations hold for clique-cover polynomials and chromatic polynomials. As applications, we find an efficient algorithm that computes these graph polynomials for cographs. We also give explicit formulas to compute the number of Hamiltonian paths and cycles in complete multipartite graphs.
- journal
- Discrete Mathematics 350 (2027), no. 3, 115528
- fields
- Combinatorics