Paperlane

no. 16 · Tuesday 17 November 2026

Duality Relations of Graph Polynomials

Medet Jumadildayev

math.CO · v2

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
pdf ↗ page arXiv:2512.15351 ↗