# zbMATH — the first resource for mathematics

Weakly distinguishing graph polynomials on addable properties. (English) Zbl 1451.05122
Summary: A graph polynomial $$P$$ is weakly distinguishing if for almost all finite graphs $$G$$ there is a finite graph $$H$$ that is not isomorphic to $$G$$ with $$P(G)=P(H)$$. It is weakly distinguishing on a graph property $$\mathcal{C}$$ if for almost all finite graphs $$G\in\mathcal{C}$$ there is $$H \in \mathcal C$$ that is not isomorphic to $$G$$ with $$P(G)=P(H)$$. We give sufficient conditions on a graph property $$\mathcal{C}$$ for the characteristic, clique, independence, matching, and domination and $$\xi$$ polynomials, as well as the Tutte polynomial and its specializations, to be weakly distinguishing on $$\mathcal{C}$$. One such condition is to be addable and small in the sense of C. McDiarmid et al. [J. Comb. Theory, Ser. B 93, No. 2, 187–205 (2005; Zbl 1056.05128)]. Another one is to be of genus at most $$k$$.
##### MSC:
 05C31 Graph polynomials 05C10 Planar graphs; geometric and topological aspects of graph theory 05C30 Enumeration in graph theory 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C80 Random graphs (graph-theoretic aspects)
Full Text: