Abstract

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\left(G\right)=P\left(H\right)$. It is weakly distinguishing on a graph property $\mathcal{𝒞}$ if for almost all finite graphs $G\in \mathcal{𝒞}$ there is $H\in \mathcal{𝒞}$ that is not isomorphic to $G$ with $P\left(G\right)=P\left(H\right)$. We give sufficient conditions on a graph property $\mathcal{𝒞}$ 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{𝒞}$. One such condition is to be addable and small in the sense of C. McDiarmid, A. Steger and D. Welsh (2005). Another one is to be of genus at most $k$.

Keywords

Mathematical Subject Classification 2010

Milestones

Authors