Faculty Activities[ Edit ]
Advisor: Makowsky Johann
Abstract: A graph polynomial is weakly distinguishing (on a graph property A) if for almost all finite graphs G (in A) 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, and give sufficient conditions on graph properties C for the generating functions of induced subgraphs with property C to be weakly distinguishing.
In addition, we give sufficient conditions on graph properties A for the Tutte, the Domination and the Characteristic polynomials to be weakly distinguishing on A.