Makowsky, Johann A. and Rakita, Vsevolod - On Weakly Distinguishing Graph Polynomials

dmtcs:4949 - Discrete Mathematics & Theoretical Computer Science, April 2, 2019, vol. 21 no. 1, ICGT 2018
On Weakly Distinguishing Graph Polynomials

Authors: Makowsky, Johann A. and Rakita, Vsevolod

A univariate graph polynomial P(G;X) is weakly distinguishing if for almost all finite graphs G there is a finite graph H with P(G;X)=P(H;X). We show that the clique polynomial and the independence polynomial are weakly distinguishing. Furthermore, we show that generating functions of induced subgraphs with property C are weakly distinguishing provided that C is of bounded degeneracy or tree-width. The same holds for the harmonious chromatic polynomial.


Source : oai:arXiv.org:1810.13300
Volume: vol. 21 no. 1, ICGT 2018
Published on: April 2, 2019
Submitted on: November 1, 2018
Keywords: Mathematics - Combinatorics


Share