Johann A. Makowsky ; Vsevolod Rakita - 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 PolynomialsArticle

Authors: Johann A. Makowsky ; Vsevolod Rakita

    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.

    Volume: vol. 21 no. 1, ICGT 2018
    Published on: April 2, 2019
    Accepted on: March 25, 2019
    Submitted on: November 1, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 545 times.
    This article's PDF has been downloaded 253 times.