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\).
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: DOI