This article is available for purchase or by subscription. See below.
Abstract
|
A graph polynomial
is weakly distinguishing if for almost all finite graphs
there is a finite
graph
that is not
isomorphic to
with
.
It is weakly distinguishing on a graph property
if for almost all
finite graphs
there
is
that is not
isomorphic to
with
.
We give sufficient conditions on a graph property
for the characteristic, clique, independence, matching, and domination and
polynomials,
as well as the Tutte polynomial and its specializations, to be weakly distinguishing on
. 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
.
|
PDF Access Denied
We have not been able to recognize your IP address
3.94.202.151
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journal-recommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for
USD 40.00:
Keywords
graph polynomials, random graphs, Bollobás–Pebody–Riordan
conjecture, addable graph classes
|
Mathematical Subject Classification 2010
Primary: 05C31
Secondary: 05C10, 05C30, 05C69, 05C80
|
Milestones
Received: 5 December 2019
Revised: 1 March 2020
Accepted: 19 March 2020
Published: 15 October 2020
|
|