Weakly distinguishing graph polynomials on addable properties

Publication date 10 November 2020

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 (G) = P (H)

. It is weakly distinguishing on a graph property

m a t h c a l C

if for almost all finite graphs

G i n m a t h c a l C

there is

H i n m a t h c a l C

that is not isomorphic to

G

with

P (G) = P (H)

. We give sufficient conditions on a graph property

m a t h c a l C

for the characteristic, clique, independence, matching, and domination and

x i

polynomials, as well as the Tutte polynomial and its specialisations, to be weakly distinguishing on

m a t h c a l C

. 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

.

Recommendations

Cited in

(2)

This page was built for publication: Weakly distinguishing graph polynomials on addable properties