# Weakly Distinguishing Graph Polynomials on Addable Properties

Johann A. Makowsky  Department of Computer Science, Technion - IIT, Haifa,
Israel<EMAIL_ADDRESS>and  Vsevolod Rakita⋆ Department of
Mathematics, Technion - IIT, Haifa, Israel<EMAIL_ADDRESS>
(Date: October 12, 2019)

###### 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 $\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 specialisations, to be weakly distinguishing on
$\mathcal{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$.

###### Key words and phrases:

Graph polynomials, Random graphs, Addable graph classes, Bollobás-Pebody-
Riordan Conjecture

###### 2010 Mathematics Subject Classification:

05, 05C10, 05C30, 05C31, 05C69, 05C80

(⋆) Partially supported by a Jacobs Scholarship for excellent students.

###### Contents

  1. 1 Introduction and Preliminaries
  2. 2 Comparing graph polynomials
  3. 3 Addable Properties and graphs of genus $k$
    1. 3.1 Small addable classes
    2. 3.2 Graphs With Genus at Most $k$
  4. 4 The Characteristic Polynomial
  5. 5 The Domination Polynomial
  6. 6 The $\xi$ Polynomial
  7. 7 $\xi$-invariants
    1. 7.1 The generalized chromatic polynomial
    2. 7.2 The matching polynomial
    3. 7.3 Independence and clique polynomial
    4. 7.4 The Tutte polynomial
  8. 8 Conclusion

##  1\. Introduction and Preliminaries

We consider only, unless otherwise stated, simple (finite, loopless,
undirected graphs with no parallel edges) graphs with vertices labeled
$1,...,n$. A graph property is a family of graphs that is closed under
isomorphisms. For a graph property $\mathcal{C}$, denote by $\mathcal{C}(n)$
the graphs of order $n$ in $\mathcal{C}$. We only consider properties such
that $\mathcal{C}(n)$ is non empty for all sufficiently large $n$.

Let $P$ be a graph polynomial. We say that two non isomorphic graphs $G$ and
$H$ are $P$-mates if $P(G)=P(H)$, and that $G$ is $P$ unique if it has no $P$
mates. $P$ is trivial if all graphs $G,H$ are $P$-mates. $P$ is complete if
all graphs $G$ are $P$-unique.

In this paper we investigate conditions which imply that almost all graphs in
a graph property $\mathcal{C}$ have a $P$-mate. More formally, we give the
following definitions:

Let $P$ be a graph polynomial, and denote by $\mathcal{G}(n)$ the family of
graphs of order $n$ with vertices labeled $1,...n$, and by $U_{P}(n)$ the set
of $P$ unique graphs of order $n$.

######  Definition 1.1.

$P$ is weakly distinguishing if

$\lim_{n\rightarrow\infty}\dfrac{|U_{P}(n)|}{|\mathcal{G}(n)|}=0$

and that $P$ is almost complete if

$\lim_{n\rightarrow\infty}\dfrac{|U_{P}(n)|}{|\mathcal{G}(n)|}=1$

In [5], Bollobás, Pebody and Riordan conjectured:

######  Conjecture 1 (BPR-conjecture).

The chromatic and Tutte polynomials are almost complete.

In [17], the analogous question for $r$-regular hypergraphs was considered,
and for $r\geq 3$ the conjecture was refuted. In [24] it was observed, as a
remark in the conclusions, that the independence polynomial $In(G;x)$,
discussed in Section 7.3, is weakly distinguishing on all finite graphs. In
[15], it was proven that an infinite number of graph polynomials, among them
the independence, clique and harmonious polynomials, are weakly
distinguishing.

A natural way to approach the question whether a graph polynomial $P$ is
weakly distinguishing, almost complete or otherwise, is to ask, given a graph
property $\mathcal{C}$, whether almost all graphs in $\mathcal{C}$ are $P$
unique in $\mathcal{C}$. Let $\mathcal{C}$ be a graph property and denote by
$U_{P,\mathcal{C}}(n)=\\{G\in\mathcal{C}(n):G$ has no $P$-mate in
$\mathcal{C}\\}$.

######  Definition 1.2.

$P$ is weakly distinguishing on $\mathcal{C}$ if

$\lim_{n\rightarrow\infty}\dfrac{|U_{P,\mathcal{C}}(n)|}{|\mathcal{C}(n)|}=0,$

and that $P$ is almost complete on $\mathcal{C}$ if

$\lim_{n\rightarrow\infty}\dfrac{|U_{P,\mathcal{C}}(n)|}{|\mathcal{C}(n)|}=1.$

In this paper we prove that many well studied graph polynomials are weakly
distinguishing in infinitely many graph properties $\mathcal{C}$, Example 3.2.
However, all these properties $\mathcal{C}$ are small (in the sense that they
are sets of measure $0$ in the collection of all graphs), so these results do
not imply that any of the above polynomials are weakly distinguishing or
almost complete for arbitrary properties $\mathcal{C}$.

The graph polynomials for which we show that they are weakly distinguishing
for $\mathcal{C}$ include the characteristic polynomial, the domination
polynomial, and the $\xi$-polynomial, which is a generalization of the both
the matching and the Tutte polynomial. These three polynomials are mutually
incomparable in distinctive power by Proposition 2.3. Once we know that $\xi$
is weakly distinguishing for a graph property $\mathcal{C}$, the holds also
for all the graph polynomials which are substitution instances of $\xi$ in
$\mathcal{C}$. This includes the matching polynomials, the independence
polynomial, the chromatic polynomial, the Tutte polynomial, the Euler
polynomial, and many others, see Section 7.

This paper is organized as follows: In Section 2 we introduce a method to
compare distinctive power of graph polynomials and formulate how to use it
(Lemma A. In Section 3, we give a graph theoretic background on addable
properties, and graphs of genus at most $k$, and formulate our main tools,
Lemma B and Lemma C. In Sections 4 and 5 we prove our results: Theorems
4.4,4.7 for the characteristic polynomial, Theorems 5.5,5.8 for the domination
polynomial. In Section 6 we prove the same for the $\xi$-polynomial and in
Section we apply Lemma A to derive the corresponding results for the matching
polynomials, the independence polynomial, the chromatic polynomial, the Tutte
polynomial, the Euler polynomial, and many others.

In Section 8 we draw conclusions and present open problems.

#### Acknowledgements

Preliminary versions of our results were presented at the 19th International
Conference on Random Structures and Algorithms, 15 to 19 July 2019, Zürich,
Switzerland. The results of Sections 6 and 7 were partially obtained during
Seminar 19401 in Dagstuhl (Comparative Theory for Graph Polynomials) in
October 2019. We want to thank the participants of the Dagstuhl Seminar Delia
Garijo, Anna de Mier, Marc Noy, Elena Ravve and Peter Tittmann for valuable
discussions and comments. Thanks go especially to Peter Tittmann for his
guidance and comments about invariants derivable from $\xi$-polynomial, which
helped us formulating Section 7.

##  2\. Comparing graph polynomials

In this section we provide a tool (Lemma A) which allows us to show that many
graph polynomials are weakly distinguishing.

######  Definition 2.1.

Let $\mathcal{C}$ be a graph property, $P$ and $Q$ be two graph polynomials
and $G$ and $H$ two finite graphs.

  1. (i)

$G$ and $H$ are similar if they have the same number of vertices, edges and
connected components.

  2. (ii)

$P<_{d.p}^{\mathcal{C}}Q$ or $Q$ is at least as distinctive as $P$ in
$\mathcal{C}$ if for all graphs $G,H\in\mathcal{C}$,
$Q(G;\bar{x})=Q(H;\bar{x})$ implies $P(G;\bar{y})=P(H;\bar{y})$.

  3. (iii)

$P\sim_{d.p}^{\mathcal{C}}Q$ or $P$ and $Q$ are of the same distinctive power
in $\mathcal{C}$ if $P<_{d.p}^{\mathcal{C}}Q$ and $Q<_{d.p}^{\mathcal{C}}P$.

  4. (iv)

$P<_{s.d.p}^{\mathcal{C}}Q$ or $P$ and $Q$ are of the same distinctive power
in $\mathcal{C}$ on similar graphs if if for all similar graphs
$G,H\in\mathcal{C}$, $Q(G;\bar{x})=Q(H;\bar{x})$ implies
$Q(G;\bar{y})=Q(H;\bar{y})$.

  5. (v)

$P\sim_{s.d.p}^{\mathcal{C}}Q$ if $P<_{s.d.p}^{\mathcal{C}}Q$ and
$Q<_{s.d.p}^{\mathcal{C}}P$.

  6. (vi)

For all graph properties $\mathcal{C}$ $P<_{d.p}^{\mathcal{C}}Q$ implies
$P<_{s.d.p}^{\mathcal{C}}Q$.

If $\mathcal{C}$ consists of all finite graphs, we omit it.

The partial preorders $<_{d.p.}$ and $<_{s.d.p.}$ between graph polynomials
(or general graph invariants) are studied extensively in [16]. A complete
(trivial) graph polynomial is a maximal (minimal) element with respect to
$<_{d.p.}$

######  Example 2.2.

  1. (i)

The chromatic polynomial $\chi(G;x)$ and the Tutte polynomial satisfy
$\chi(G;x)<_{s.d.p.}T(G;x,y)$ but not $\chi(G;x)<_{d.p.}T(G;x,y)$, see Section
7, because $T(;x,y)$ does not determine the order of $G$ in the presence of
isolated vertices.

  2. (ii)

The characteristic polynomial $P_{A}(G;x)$ and the (defect aka acyclic)
matching polynomial $\mu(G;x)$ from Section 7.2 are $d.p.$-equivalent on
forests, see [10].

  3. (iii)

Let $\bar{G}$ be the (loopless) complement graph of a simple graph $G$, and
$P(G;\bar{x})$ be a (possibly multivariate) graph polynomial. Put
$\bar{P}(G;\bar{x})=P(\bar{G},\bar{x})$. Then
$\bar{P}(G;\bar{x})\sim_{d.p.}P(G,\bar{x})$.
If we relativize this to a graph property $\mathcal{C}$
$\bar{P}(G;\bar{x})\sim_{d.p.}^{\mathcal{C}}P(G,\bar{x})$ holds provided
$\mathcal{C}$ is closed under complement graphs.

######  Proposition 2.3.

The following graph polynomials are pairwise incomparable by $<_{s.d.p}$:

  1. (i)

The chromatic polynomial $\chi(G;x)$ and the independence polynomial $In(G;x)$
from Section 7.

  2. (ii)

The characteristic polynomial $P_{A}(G,x)$ from Sections 4 and the chromatic
polynomial $\chi(G;x)$.

  3. (iii)

The characteristic polynomial $P_{A}(G;x)$ and the independence polynomial
$In(G;x)$.

  4. (iv)

The characteristic polynomial $P_{A}(G,x)$ and the domination polynomial
$Dom(G;x)$. from Sections 4 and 5.

  5. (v)

The characteristic polynomial and the $\xi$-polynomial from Section 6.

  6. (vi)

The domination polynomial and the $\xi$-polynomial.

###### Proof.

The first three examples are from [16].

For (iv)-(vi) we first note that all graphs of order less than $8$ and all
trees of order less than $10$ are $\xi$-unique, see [26].

(A): Consider the graphs $C_{4}\sqcup K_{1}$ and $S_{5}$ in Figure 1. We have
$P_{A}(S_{5},x)=P_{A}(C_{4}\sqcup K_{1},x)=x^{2}(x+2)(x-2)$.
$Dom(S_{5},1)=1$, $Dom(C_{4}\sqcup K_{1},1)=0$, and
$\xi(S_{5},x)\neq\xi(C_{4}\sqcup K_{1},x)$, since they are of order $5$.

Figure 1. $P_{A}$-mates

(B): Let $P_{5}$ and $\hat{P_{5}}$ be the graphs of order $5$ in Figure 4.
used in Corollary 5.4.
$Dom(P_{5},x)=Dom(\hat{P_{5}},x)$, since every dominating set of $\hat{P_{5}}$
is also a dominating set of $P_{5}$.
$P_{A}(P_{5},x)=-x(x-1)(x+1)(x^{2}-3)\neq
P_{A}(\hat{(}P_{5}),x)=-x(x^{2}-x-3)(x^{2}+x-1)$, hence $P_{A}(P_{5},x)\neq
P_{A}(\hat{P_{5}},x)$.
$\xi(P_{5},x)\neq\xi(\hat{P_{5}},x)$, since both $P_{5}$ and $\hat{P_{5}}$ are
$\xi$-unique.

Figure 2. $\xi$-mates

(C): The graphs $G_{1}$ and $G_{2}$ Figure 2 are of order $10$. Therefore we
have $\xi(G_{1},x)=\xi(G_{2},x)$.
However, $Dom(G_{1};x)=x^{10}+10x^{9}+40x^{8}+82x^{7}+92x^{6}+56x^{5}+16x^{4}$
and $Dom(G_{2};x)=x^{10}+10x^{9}+41x^{8}+86x^{7}+94x^{6}+48x^{5}+9x^{4}$,
hence $Dom(G_{1},x)\neq Dom(G_{2},x)$ and
$P_{A}(G_{1};x)=x^{2}(x^{4}-x^{3}-4x^{2}+2x+3)(x^{4}+x^{3}-4x^{2}-2x+3)$ and
$P_{A}(G_{2};x)=x^{2}(x-1)(x+1)(x^{2}-2)(x^{4}-5x^{2}+3)$, hence
$P_{A}(G_{1},x)\neq P_{A}(G_{2},x)$.

Now (A) and (B) proves (iv), (A) and (C) proves (v), and (B) and (C) proves
(vi). ∎

In Section 7 we use the following observation:

######  Lemma A.

Let $P(G;\bar{x})$ and $Q(G;\bar{y})$ two graph polynomials and $\mathcal{C}$
and $\mathcal{D}$ be graph properties with $\mathcal{D}\subseteq\mathcal{C}$.
Assume that $P<_{s.d.p}^{\mathcal{C}}Q$ and $Q$ is weakly distinguishing in
$\mathcal{C}$. Then also $P$ is weakly distinguishing in $\mathcal{C}$ but not
necessarily in $\mathcal{D}$.

###### Proof.

Clearly, $P<_{s.d.p}^{\mathcal{C}}Q$ implies that $U_{P}(n)\subseteq
U_{Q}(n)$. Hence

$\lim_{n\rightarrow\infty}\dfrac{|U_{Q}(n)|}{|\mathcal{G}(n)|}\leq\lim_{n\rightarrow\infty}\dfrac{|U_{P}(n)|}{|\mathcal{G}(n)|}.$

∎

##  3\. Addable Properties and graphs of genus $k$

We discuss properties on which the Tutte, Domination, Matching, $\xi$, Clique
and Characteristic polynomials are weakly distinguishing. These properties
were discussed in [20] and [18].

###  3.1. Small addable classes

######  Definition 3.1.

We say a graph property $\mathcal{A}$ is decomposable if a graph is in
$\mathcal{A}$ if and only if each of its connected components are in
$\mathcal{A}$.
We say a graph property $\mathcal{A}$ is bridge addable if for each graph
$G\in\mathcal{A}$ and every two vertices $u,v$ in different components of $G$
the graph obtained by adding an edge between $u$ and $v$ is also in
$\mathcal{A}$.
We say a graph property $\mathcal{A}$ is addable if it is decomposable and
bridge addable.

######  Example 3.2.

The following properties are easily seen to be addable:

  1. (i)

Planar graphs;

  2. (ii)

Outerplanar graphs;

  3. (iii)

Series Parallel graphs;

  4. (iv)

Graphs with tree-width at most $k$ for $k\geq 2$;

  5. (v)

$k$-colorable graphs for $k\geq 2$;

  6. (vi)

Graphs with no cycles of length greater than $k$;

  7. (vii)

Graphs with no $K_{k}$ minor for $k\geq 2$.

Let $\mathcal{A}$ be a graph property. If $\mathcal{A}$ is minor closed (that
is, closed under deletion of vertices and edges, and under contraction of
edges) the Graph Minor theorem says that $\mathcal{A}$ is characterized by a
finite set of forbidden minors (see [14] for more on graph minors and the
graph minor theorem). We can characterize addable minor closed graph
properties in terms of their forbidden minors:

######  Proposition 3.3 ([19]).

Let $\mathcal{A}$ be a minor closed graph property. Then $\mathcal{A}$ is
addable if and only if each excluded minor of $\mathcal{A}$ is 2-connected.

Note that any non empty, minor closed addable graph property $\mathcal{A}$
contains all forests, as it contains the graph with a single vertex, and is
closed under taking disjoint unions of graphs in $\mathcal{A}$ and under
adding edges between different components.

In addition to being addable, we will require the properties we consider to be
small:

######  Definition 3.4.

We say that a graph property $\mathcal{A}$ is small if there exists a constant
$a>0$ such that $|\mathcal{A}_{n}|\leq a^{n}n!$ for all sufficiently large
$n$.

The following result of Norine et. al. is convenient:

######  Theorem 3.5 ([23]).

Let $\mathcal{C}$ be a proper minor closed graph property. Then $\mathcal{C}$
is small.

Let $H$ be a graph on vertex set $\\{1,...,h\\}$ and let $G$ be a graph on the
vertex set $\\{1,...,n\\}$ where $n>h$. Let $W\subseteq V(G)$ with $|W|=h$,
and let the root $r_{W}$ denote the least element in $W$. We say that $W$ is a
pendant appearance of $H$ in $G$ if (a) the increasing bijection from
$\\{1,...,h\\}$ to $W$ gives an isomorphism between $H$ and and the induced
subgraph $G[W]$ of $G$, and (b) there exists exactly one edge between $W$ and
$V(G)-W$, and this edge is incident with the root $r_{W}$. Our method for
proving graph polynomials are weakly distinguishing will relay on the
following theorem:

######  Theorem 3.6 (McDiarmid,Steger,Welsh [20]).

Let $\mathcal{C}$ be a non-empty, addable, and small graph property, let
$H\in\mathcal{C}$ be a connected graph, and let $R_{n}$ be a random graph
selected uniformly at random from the graphs of order $n$ in $\mathcal{C}$.
Denote by $f_{H}(R_{n})$ the number of pendant appearances of $H$ in $R_{n}$.
Then there are constants $\alpha>0$,$n_{0}\in\mathbb{N}$ such that for all
$n>n_{0}$,

$\mathbb{P}[f_{H}(R_{n})\leq\alpha n]<e^{-\alpha n}$

For our purposes, we shall only need a weaker corollary of theorem 3.6:

######  Corollary 3.7.

Let $\mathcal{A}$ be an addable proper minor closed graph property, $H$ a
fixed connected graph in $\mathcal{A}$. Denote by $\mathcal{A}^{\prime}_{n}$
the set of all $n$ vertex graphs $G\in\mathcal{A}$ that have at least one
pendent appearance of $H$. Then
$\lim_{n\rightarrow\infty}\frac{|\mathcal{A}^{\prime}_{n}|}{|\mathcal{A}_{n}|}=1$.

All the properties listed in example 3.2 are addable and minor closed, hence
the corollary applies to them. Using this corollary, we get:

######  Lemma B.

Let $P$ be a graph polynomial, $\mathcal{A}$ a small addable graph property.
If there is a fixed $H\in\mathcal{A}$ such that if a graph $G\in\mathcal{A}$
has a pendant appearance of $H$, $G$ has a $P$ mate
$G^{\prime}\in\mathcal{A}$, then $P$ is weakly distinguishing on
$\mathcal{A}$.

###### Proof.

By corollary 3.7, almost all graphs $G\in\mathcal{A}$ have a pendant
appearance of $H$, and hence almost all graphs $G\in\mathcal{A}$ have a
$P$-mate, so $P$ is weakly distinguishing on $\mathcal{A}$. ∎

###  3.2. Graphs With Genus at Most $k$

Let $G$ be a graph.The genus of $G$, denoted $g(G)$, is the minimal genus of a
surface in which $G$ can be embedded (for more on graphs embedded in surfaces
see, for example, [13, 22]). It is easy to see that $g(G)$ is well defined, as
for all $G$, $g(G)\leq|E(G)|$. For $k\in\mathbb{N}$, denote by
$\mathcal{C}_{k}$ the property of graphs with genus at most $k$. Note that in
general $\mathcal{C}_{k}$ is not addable - for instance, the genus of $K_{5}$,
the complete graph with 5 vertices, is 1, but the genus of a disjoint union of
two copies of $K_{5}$ has genus 2- so we can not apply theorem 3.6 to
$\mathcal{C}_{k}$. However, the same result does hold for $\mathcal{C}_{k}$
with a slight modification:

######  Theorem 3.8 (McDiarmid [18]).

Let $H$ be a connected graph, $k\in\mathbb{N}$, and let $R_{n}$ be a random
graph selected uniformly at random from the graphs of order $n$ in
$\mathcal{C}_{k}$. Denote by $f_{H}(R_{n})$ the number of pendant appearances
of $H$ in $R_{n}$. Then there are constants $\alpha>0$,$n_{0}\in\mathbb{N}$
such that for all $n>n_{0}$,

$\mathbb{P}[f_{H}(R_{n})\leq\alpha n]<e^{-\alpha n}$

Again, we only need a weaker corollary of this theorem:

######  Corollary 3.9.

Let $H$ a fixed connected planar graph, $k\in\mathbb{N}$ and let
$\mathcal{A}=\mathcal{C}_{k}$. Denote by $\mathcal{A}^{\prime}_{n}$ the set of
all $n$ vertex graphs $G\in\mathcal{A}$ that have at least one pendent
appearance of $H$. Then
$\lim_{n\rightarrow\infty}\frac{|\mathcal{A}^{\prime}_{n}|}{|\mathcal{A}_{n}|}=1$.

Using this corollary, we get:

######  Lemma C.

Let $P$ be a graph polynomial, $\mathcal{C}_{k}$ the property of graphs with
genus at most $k$. If there is a planar graph $H$ such that if a graph $G$ has
a pendant appearance of $H$, $G$ has a $P$ mate
$G^{\prime}\in\mathcal{C}_{k}$, then $P$ is weakly distinguishing on
$\mathcal{C}_{k}$.

###### Proof.

By corollary 3.9, almost all graphs $G\in\mathcal{C}_{k}$ have a pendant
appearance of $H$, and hence almost all graphs $G\in\mathcal{C}_{k}$ have a
$P$-mate, so $P$ is weakly distinguishing on $\mathcal{C}_{k}$. ∎

##  4\. The Characteristic Polynomial

######  Definition 4.1.

Let $G$ be a graph, and denote by $A_{G}$ its adjacency matrix. The
characteristic polynomial of $G$, denoted $P_{A}(G)$ is defined as the
characteristic polynomial of $A_{G}$. The roots of $P_{A}(G)$ are referred to
as the spectrum of $G$.
A $P_{A}$-unique graph is usually referred to as a graph determined by its
spectrum, and if $G$ and $H$ are two non isomorphic graphs such that
$P_{A}(G)=P_{A}(H)$, $G$ and $H$ are said to be cospectral.

The characteristic polynomial and particularly its roots are a widely studied
topic, see e.g. [6] for an introduction. A classic result of Schwenk states
that almost all trees are not determined by their spectrum (see [25] for
details). Using corollary 3.7, we can extend this result to all small addable
graph properties.

We use the following recurrence relation for the characteristic polynomial:

######  Lemma 4.2 (see [7]).

Let $G_{1}$ and $G_{2}$ be two graphs, and let $v_{1}\in V(G_{1})$ ,$v_{2}\in
V(G_{2})$. Denote by $H$ the graph obtained from the disjoint union of $G_{1}$
and $G_{2}$ by adding an edge from $v_{1}$ to $v_{2}$. Then

(4.1) $\displaystyle
P_{A}(H,x)=P_{A}(G_{1},x)P_{A}(G_{2},x)-P_{A}(G_{1}-v_{1},x)P_{A}(G_{2}-v_{2},x)$

Consider the graphs in Figure 3 (considered by Schwenk in [25]).

Figure 3. Cospectral Graphs

Note that $S$ and $R$ are isomorphic, and we can check that

$P_{A}(S-v,x)=P_{A}(R-u,x)=x^{8}-6x^{6}+10x^{4}-4x^{2}$

Thus, we get:

######  Lemma 4.3.

Let $G_{S}$ be a graph with a pendent appearance of $S$ rooted at $v$. Denote
by $G_{R}$ the graph obtained from $G$ by replacing the pendant appearance of
$S$ in $G$ with a pendant appearance of $R$, rooted at $u$. Then $G_{S}$ and
$G_{R}$ are cospectral mates.

###### Proof.

Denote by $w\in V(G_{S})$ the vertex adjacent to $v$ that is not in the
pendant appearance of $S$, and by $H$ the graph obtained from $G_{S}$ by
deleting all the vertices in the pendant appearance of $S$. By applying
relation 4.1 to $G_{S}$ with the edge $wv$, we get

$P_{A}(G_{S},x)=P_{A}(S,x)P_{A}(H,x)-P_{A}(S-v,x)P_{A}(H-w,x)$

By applying relation 4.1 to $G_{R}$ with the edge $wu$ we get

$P_{A}(G_{R},x)=P_{A}(R,x)P_{A}(H,x)-P_{A}(R-u,x)P_{A}(H-w,x)$

But since $P_{A}(R,x)=P_{A}(S,x)$ and $P_{A}(S-v,x)=P_{A}(R-u,x)$, we get that
$P_{A}(G_{S},x)=P_{A}(G_{R},x)$, so $G_{S}$ and $G_{R}$ are cospectral mates.
∎

Note that $S$ and $R$, as unrooted graphs, are isomorphic. Thus, we have:

######  Theorem 4.4.

Let $\mathcal{A}$ be a small addable graph property such that
$S\in\mathcal{A}$. Then $P_{A}$ is weakly distinguishing on $\mathcal{A}$.

###### Proof.

From lemmas B and 4.3 we get that $P_{A}$ is weakly distinguishing on
$\mathcal{A}$. ∎

######  Corollary 4.5.

Let $\mathcal{A}$ be a proper minor closed addable graph property. Then
$P_{A}$ is weakly distinguishing on $\mathcal{A}$.

###### Proof.

Since all forests are in $\mathcal{A}$, and $S$ is a tree, by theorems 4.4 and
3.5, $P_{A}$ is weakly distinguishing on $\mathcal{A}$. ∎

Since all the properties in list 3.2 are addable and minor closed, we have:

######  Corollary 4.6.

$P_{A}$ is weakly distinguishing on all the properties listed in example 3.2.

Similarly, we get:

######  Theorem 4.7.

Denote by $\mathcal{C}_{k}$ the class of graphs of genus at most $k$. Then
$P_{A}$ is weakly distinguishing on $\mathcal{C}_{k}$ for all
$k\in\mathbb{N}$.

###### Proof.

Since $S$ is a tree, from lemmas C and 4.3 we get that $P_{A}$ is weakly
distinguishing on $\mathcal{C}_{k}$. ∎

Instead of the characteristic polynomial $P_{A}$, which is based on the
adjacency matrix, one can also look at the analogue graph polynomial $P_{L}$
which is based on the Laplacian matrix $L_{G}=D_{G}-A_{G}$, where $D_{G}$ is
the diagonal matrix with diagonal elements $d_{v,v}=deg(v)$ for each $v\in
V(G)$. Now $P_{L}(G;x)$ is the characteristic polynomial of $L_{G}$. An early
survey about the Laplacian polynomial may be found in [21]. The graph
polynomials are $d.p.$-equivalent on regular graphs, but $d.p.$-incomparable
on all finite graphs, cf. [6] and [16]. Our proofs of Theorems 4.4 and 4.7 do
not work for $P_{L}(G;x)$.

######  Problem 4.1.

Find two graphs $R$ and $S$ which can be used two prove the analogue of
Theorems 4.4 and 4.7.

##  5\. The Domination Polynomial

The Domination Polynomial is the generating function of dominating sets in a
given graph $G$. More formally,

######  Definition 5.1.

Let $G$ be a graph. A set $S\subseteq V(G)$ is called a dominating set if for
every $v\in V(G)$, either $v\in S$ or $v$ has a neighbor $u\in S$. Define
$Dom(G;x)=\sum_{S\subseteq V(G)}x^{|S|}$ where the sum is over all dominating
sets of $G$.

The Domination Polynomial was extensively studied in recent years, see [2] for
a survey. In [12], the following was observed:

######  Lemma 5.2.

Let $G$ be a graph. We say a vertex $v\in V(G)$ is a stem if it has a neighbor
$u\in V(G)$ with $deg(u)=1$. Assume $G$ has two stems $u,u^{\prime}\in G$,
$(u,u^{\prime})\in E(G)$, and denote by $G^{\prime}$ the graph resulting from
$G$ by deleting the edge $(u,u^{\prime})$. Then for every set $S\subseteq
V(G)$, $S$ is a dominating set of $G$ if and only if $S$ is a dominating set
of $G^{\prime}$.

###### Proof.

If $S$ is a dominating set of $G^{\prime}$, it is clearly also a dominating
set of $G$. On the other hand, let $S$ be a dominating set of $G$. After
deleting $(u,u^{\prime})$, the only vertices that are perhaps not dominated by
$S$ are $u,u^{\prime}$. But $u$ has a vertex of degree 1 as a neighbor, so
either it or $u$ are in $S$, and in either case $u$ is dominated. The same
applies to $u^{\prime}$. So $S$ is a dominating set of $G^{\prime}$. ∎

From this lemma, we get:

######  Theorem 5.3.

Every graph $G$ that has two distinct stems has a $Dom$-mate.

###### Proof.

This is a direct consequence of the lemma. ∎

Thus, we have:

######  Corollary 5.4.

Let $G$ be a graph that has a pendant appearance of $P_{5}$ rooted at $r$ (see
Figure 4), and let $\hat{G}$ be the graph obtained from $G$ by replacing the
pendant appearance of $P_{5}$ with a pendant appearance of $\hat{P}_{5}$
rooted at $r$. Then $G$ and $\hat{G}$ are $Dom$-mates.

Figure 4. A path of length 5

And so:

######  Theorem 5.5.

Let $\mathcal{A}$ be a small addable graph property such that
$P_{5},\hat{P}_{5}\in\mathcal{A}$. Then $Dom$ is weakly distinguishing on
$\mathcal{A}$.

###### Proof.

From lemma B and corollary 5.4 we get that $Dom$ is weakly distinguishing on
$\mathcal{A}$. ∎

######  Corollary 5.6.

Let $\mathcal{A}$ be a proper minor closed addable graph property, such that
$\hat{P}_{5}\in\mathcal{A}$. Then $Dom$ is weakly distinguishing on
$\mathcal{A}$

###### Proof.

Note that, since all forests are in $\mathcal{A}$, $P_{5}\in\mathcal{A}$, and
hence from theorems 5.5 and 3.5 $Dom$ is weakly distinguishing on
$\mathcal{A}$. ∎

As in the previous sections, we have:

######  Corollary 5.7.

$Dom$ is weakly distinguishing on all the properties listed in example 3.2.

Similarly, we get:

######  Theorem 5.8.

Denote by $\mathcal{C}_{k}$ the property of graphs of genus less than $k$.
Then $Dom$ is weakly distinguishing on $\mathcal{C}_{k}$ for all
$k\in\mathbb{N}$.

###### Proof.

Since $P_{5}$ and $\hat{P}_{5}$ are planar, from lemma C and corollary 5.4 we
get that $Dom$ is weakly distinguishing on $\mathcal{C}_{k}$. ∎

##  6\. The $\xi$ Polynomial

The $\xi$ polynomial, introduced in [3][4], generalizes the matching and the
Tutte polynomial. It is defined via a recurrence relation:

######  Definition 6.1.

Let $G$ be a graph. Define the tri-variate polynomial $\xi(G;x,y,z)$ using the
recursive relation

(6.1) $\displaystyle\xi(G;x,y,z)=\xi(G-e;x,y,z)+y\xi(G/e;x,y,z)+z\xi(G\dagger
e;x,y,z)$ $\xi(G\sqcup H;x,y,z)=\xi(G;x,y,z)\xi(H;x,y,z)$

with the base conditions $\xi(K_{1};x,y,z)=x$ and $\xi(\emptyset;x,y,z)=1$.

Let $G=(V(G),E(G))$ be a graph and $A\subseteq E(G)$. We denote by $G\langle
A\rangle$ the graph $(V(G),A)$, the spanning subgraph of $A$ in $G$. An
alternative representation of the $\xi$ polynomial was introduced by Trinks in
[26]:

######  Definition 6.2.

Let $G$ be a graph. The covered components polynomial $C(G;x,y,z)$ of $G$ is
defined as:

$C(G;x,y,z)=\sum_{A\subseteq E(G)}x^{k(G\langle A\rangle)}y^{|A|}z^{c(G\langle
A\rangle)}$

were $G\langle A\rangle$ is the graph $(V(G),A)$, $k(G\langle A\rangle)$ is
the number of connected components of $G\langle A\rangle$ and $c(G\langle
A\rangle)$ is the number of covered connected components of $G\langle
A\rangle$, that is connected components in $G\langle A\rangle$ with at least
one edge.

We sometimes write $C(G)$ for $C(G;x,y,z)$ to simplify long expressions. The
two definitions are connected via the following result:

######  Proposition 6.3 ([26]).

For all graphs $G$,

(6.2) $\displaystyle C(G;x,y,z)=\xi(G;x,y,xyz-xy)$

######  Corollary 6.4.

Let $G$ and $H$ be graphs. Then $C(G;x,y,z)=C(H;x,y,z)$ if and only if
$\xi(G;x,y,z)=\xi(H;x,y,z)$

We will use the following recurrence relation:

######  Theorem 6.5 ([26]).

Let $G_{1},G_{2}$ be graphs, and $v_{1}\in V(G_{1}),v_{2}\in V(G_{2})$. Let
$H$ be the graph obtained from $G_{1}$ and $G_{2}$ by identifying $v_{1}$ with
$v_{2}$. Then the following holds:

$\displaystyle C(G)=(\frac{1}{xz}+\frac{2}{x})C(G_{1})C(G_{2})+$
$\displaystyle(-\frac{1}{z}-1)\left[C(G_{1})C(G_{2}-v_{2})+C(G_{1}-v_{1})C(G_{2})\right]+$
(6.3) $\displaystyle(\frac{x}{z}+x)C(G_{1}-v_{1})C(G_{2}-v_{2})$

Consider the graph $S$ in Figure 5.

Figure 5. A tree with pseudosimilar vertices

We use the graphs in Figure 5, together with theorem 6.5 to prove:

######  Lemma 6.6.

Let $G_{v}$ be a graph with a pendent appearance of $S$ (depicted in Figure 5)
rooted at $v$, and let $G_{u}$ be the graph obtained from $G_{v}$ by replacing
the pendant appearance of $S$ rooted at $v$ by a pendant appearance of $S$
rooted at $u$. Then $G_{v}$ and $G_{u}$ are $C$ mates.

###### Proof.

We apply relation 6.5 to $G_{v}$, with $G_{1}=S$ and $G_{2}$ being the graph
$H_{1}$ obtained from $G_{v}$ by replacing the pendant appearance of $S$ with
a single vertex $w$. We get:

$\displaystyle C(G_{v})=(\frac{1}{xz}+\frac{2}{x})C(S)C(H_{1})+$
$\displaystyle(-\frac{1}{z}-1)\left[C(S)C(H_{1}-w)+C(S-v)C(H_{1})\right]+$
(6.4) $\displaystyle(\frac{x}{z}+x)C(S-v)C(H_{1}-w)$

Similarly, we apply relation 6.5 to $G_{u}$, with $G_{1}=S$ and $G_{2}$ being
the graph $H_{2}$ obtained from $G_{u}$ by replacing the pendant appearance of
$S$ with a single vertex $w$. We get:

$\displaystyle C(G_{u})=(\frac{1}{xz}+\frac{2}{x})C(S)C(H_{2})+$
$\displaystyle(-\frac{1}{z}-1)\left[C(S)C(H_{2}-w)+C(S-u)C(H)\right]+$
$\displaystyle(\frac{x}{z}+x)C(S-u)C(H_{2}-w)$

Note that $H_{1}\cong H_{2}$, $H_{1}-w\cong H_{2}-w$, and $S-v\cong S-u$, and
hence $C(G_{v})=C(G_{u})$. ∎

As a direct consequence of lemma 6.6 and corollary 6.4, we have:

######  Corollary 6.7.

Let $G_{v}$ be a graph with a pendent appearance of $S$ (depicted in Figure 5)
rooted at $v$, and let $G_{u}$ be the graph obtained from $G_{v}$ by replacing
the pendant appearance of $S$ rooted at $v$ by a pendant appearance of $S$
rooted at $u$. Then $G_{v}$ and $G_{u}$ are $\xi$ mates.

Thus, we have:

######  Theorem 6.8.

Let $\mathcal{A}$ be a small addable graph property such that
$S\in\mathcal{A}$. Then $\xi$ is weakly distinguishing on $\mathcal{A}$.

###### Proof.

From lemma B and corollary 6.7 we get that $\xi$ is weakly distinguishing on
$\mathcal{A}$. ∎

######  Corollary 6.9.

Let $\mathcal{A}$ be a proper minor closed addable graph property. Then $\xi$
is weakly distinguishing on $\mathcal{A}$.

###### Proof.

Note that, since all forests are in $\mathcal{A}$, $S\in\mathcal{A}$, and
hence from theorems 6.8 and 3.5, $M$ is weakly distinguishing on
$\mathcal{A}$. ∎

As in the previous section, we get

######  Corollary 6.10.

$\xi$ is weakly distinguishing on all the properties listed in example 3.2.

Similarly, we get:

######  Theorem 6.11.

Denote by $\mathcal{C}_{k}$ the class of graphs of genus less than $k$. Then
$\xi$ is weakly distinguishing on $\mathcal{C}_{k}$ for all $k\in\mathbb{N}$.

###### Proof.

Since $S$ is a tree, from lemmas C and 6.7 we get that $\xi$ is weakly
distinguishing on $\mathcal{C}_{k}$. ∎

##  7\. $\xi$-invariants

In this section we investigate consequences of Theorems 6.8 and 6.11 by using
Lemma A.

From Theorem 6.8 we get:

######  Corollary 7.1.

Let $\mathcal{A}$ be a small addable graph property such that
$S\in\mathcal{A}$, and let $P$ be a graph polynomial such that
$P<_{s.d.p}^{\mathcal{C}}\xi$. Then $P$ is weakly distinguishing on
$\mathcal{A}$.

######  Corollary 7.2.

Let $\mathcal{A}$ be a proper minor closed addable graph property, and let $P$
be a graph polynomial such that $P<_{s.d.p}^{\mathcal{C}}\xi$. Then $P$ is
weakly distinguishing on $\mathcal{A}$.

From Theorem 6.11 we get:

######  Corollary 7.3.

Let $\mathcal{C}_{k}$ the class of graphs of genus less than $k$, and let $P$
be a graph polynomial such that $P<_{s.d.p}^{\mathcal{C}}\xi$. Then $P$ is
weakly distinguishing on $\mathcal{C}_{k}$ for all $k\in\mathbb{N}$.

In the sequel of this section we collect results from the literature which
show that there are many graph polynomials $P$ where we can apply this. Among
them we find the

  1. (i)

generalized chromatic polynomial from [8], including the chromatic polynomial;

  2. (ii)

the matching polynomials;

  3. (iii)

independence polynomial, including the vertex cover polynomial;

  4. (iv)

Tutte polynomial, including the flow polynomial, the reliability polynomial
and the Euler polynomial.

###  7.1. The generalized chromatic polynomial

The generalized chromatic polynomial $GC(G;x,y)$ was introduced in [8]. There
are two disjoint sets of colors $Y$, the set of proper colors, and $Z$. A
generalized coloring of a graph $G=(V,E)$ is a map $c:V\rightarrow(Y\sqcup Z)$
such that for all $(u,v)\in E$, if $c(u)\in Y$ and $c(v)\in Y$ , then
$c(u)=c(v)$. For two positive integers $x>y$, the value of the polynomial
$GC(G;x,y)$ is the number of generalized colorings by $x$ colors, where $y$ of
them are proper. The chromatic polynomial $\chi(G;x)$ is obtained for the case
$x=y$.

######  Theorem 7.4 ([4, Proposition 22]).

For all graphs $G$

$GC(G;x,y)=\xi(G;x-1,x-y).$

Therefore $\chi<_{d.p}^{\mathcal{C}}CG<_{d.p}^{\mathcal{C}}\xi$.

###  7.2. The matching polynomial

There are several variants of the matching polynomial considered in the
literature:

######  Definition 7.5.

Let $G$ be a graph with $n$ vertices. A matching in $G$ is a spanning subgraph
of $G$ in which every connected component is either an isolated vertex or two
vertices connected by a single edge. We say a matching is of size $k$ if it
has exactly $k$ edges. Denote by $m_{k}(G)$ the number of $k$ matchings in
$G$.

The matching acyclic polynomial (also known as the matching defect polynomial)
is defined as

$\mu(G;x)=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^{k}m_{k}(G)x^{n-2k}$

The matching generating polynomial is defined as

$g(G;x)=\sum_{k=0}^{\lfloor n/2\rfloor}m_{k}(G)x^{k}$

The bivariate matching polynomial of $G$ is defined as

$M(G;w_{1},w_{2})=\sum_{k=0}^{\lfloor
n/2\rfloor}m_{k}(G)w_{1}^{n-2k}w_{2}^{k}$

For an introduction to the bivariate matching polynomial, see [9]. For a
recent survey on the acyclic matching polynomial, see [11].
For our purposes, we note the following fact:

######  Fact 7.1.

All of the polynomials in definition 7.5 are of the same distinctive power on
similar graphs:.

$\mu\sim_{s.d.p}g\sim_{s.d.p}M.$

In fact, we also have $\mu\sim_{d.p}M$, but for the edgless graphs $E_{n}$ of
order $n$ we have $g(E_{n},x)=g(E_{m})$ for all $m,n\geq 1$, but
$\mu(E_{n})\neq\mu(E_{m})$.

Thus we will only consider the bivariate matching polynomial.

######  Theorem 7.6 ([4, Proposition 20]).

For all graphs $G$

$M(G;x,y)=\xi(G;x,0,y),$

therefore $M<_{s.d.p}\xi$.

###  7.3. Independence and clique polynomial

The independence polynomial is defined as

$In(G;x)=\sum_{A\subseteq E(G)}x^{|A|}$

where the graph induced graph $G[A]$ is edgless.

The vertex cover polynomial $V(G;x)$ is defined as

$VC(G;x)=\sum_{A\subseteq E(G)}x^{|A|}$

where $A$ is a vertex cover of $G$.

The following is taken from (but possibly not originally due to) [26].

######  Proposition 7.7.

For all graphs $G$ we have

  1. (i)

$In(G;x)=GC(G;x+1,1)$

  2. (ii)

$VC(G;x)=x^{n}In((G;\frac{1}{x})$

Hence, $VC\sim_{s.d.p}In<_{s.d.p}GC$.

The clique polynomial is defined as

$Cl(G;x)=\sum_{A\subseteq E(G)}x^{|A|}$

where the graph induced graph $G[A]$ is a complete graph.

We note that $In(G;x)=Cl(\bar{G})$ for simple graphs. Therefore
$In\sim_{d.p}Cl$ by Example 2.2(iii).

Both, $In(G;x)$ and $Cl(G;x)$ were shown in [15] to be weakly distinguishing
on all finite graphs. In the light of the above, $In(G;x)$ is also weakly
distinguishing on small addable graph properties, and on graphs of genus at
most $k$.

This also holds if $\mathcal{C}$ is addable, small, and closed under
complements. If $\mathcal{C}$ is addable and small, but not closed under
complements we can use the following lemma:

Figure 6. A path of length 3

######  Lemma 7.8.

Let $G_{r}$ be a graph such that $G$ has a pendant appearance of $P_{3}$ (see
Figure 6) rooted at $r$, and $G_{u}$ the graph obtained from $G_{r}$ by
replacing the pendant appearance of $P_{3}$ by a pendant appearance of $P_{3}$
rooted at $u$. Then $G_{r}$ and $G_{u}$ are clique mates.

###### Proof.

For all $k>2$, $G_{r}$ and $G_{u}$ have the same number of $k$ cliques (since
no $k$ clique can include vertices from the pendant appearance), and $G$ and
$G^{\prime}$ have the same number of vertices and edges, and hence the same
number of $1$ and $2$ cliques. So $Cl(G_{r};x)=Cl(G_{u};x)$. ∎

Thus, we have:

######  Theorem 7.9.

Let $\mathcal{A}$ be a small addable graph property such that
$P_{3}\in\mathcal{A}$. Then $Cl$ is weakly distinguishing on $\mathcal{A}$.

###### Proof.

From Lemmas B and 7.8 we get that $Cl$ is weakly distinguishing on
$\mathcal{A}$. ∎

###  7.4. The Tutte polynomial

Let $G=(V(G),E(G)$ be a graph and $A\subseteq E(G)$. We denote by $G\langle
A\rangle$ the graph $(V(G),A)$. $k(A)$ is the number of connected components
of $G\langle A\rangle$. The Tutte polynomial $T(G;x,y)$ is defined by

$T(G;x,y)=\sum_{A\subseteq E(G)}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V(G)|}.$

The partition function $Z(G;q,w)$ is defined by

$Z(G;q,w)=\sum_{A\subseteq E(G)}q^{k(F)}w^{|F|}.$

They are related by the equation

$T(G;x,y)=(x-1)^{-k(E)}(y-1)^{-|V(G)|}Z(G;(x-1)(y-1),(y-1)).$

The chromatic polynomial $\chi(G;x)$ can be obtained from the Tutte polynomial
by

$\chi(G;x)=(-1)^{|V(G)|-k(G)}x^{k(G)}T(G;(1-x),0)$

From this we get

######  Proposition 7.10.

$\chi<_{s.d.p}T\sim_{s.d.p}Z<_{d.p}C\sim_{d.p.}\xi$.

A graph is Eulerian if all its vertices have even degree. It does not have to
be connected. The Euler polynomial $\mathcal{E}(G;x)$ of a graph is defined by

$\mathcal{E}(G;x)=\sum_{A\subseteq E(G):(V,A)\mbox{ is Eulerian }}x^{|A|}.$

From [1, Chapter 10, p.468] we get that it is related to the Tutte polynomial
by

$\mathcal{E}(G;x)=(1-x)^{|E(G)-|V(G)|+k(G)}x^{|V(G)|-k(G)}T(G;\frac{1}{x},\frac{1+x}{1-x}).$

Hence we get:

######  Proposition 7.11.

$\mathcal{E}<_{s.d.p}T$.

The flow polynomial $Fl(G,x)$ and the reliability polynomial $R(G;p)$ are
related to the Tutte polynomial by

$\displaystyle FL(G;x)=(-1)^{|E(G)-|V(G)|+k(G)}T(G;0,1-x)$ $\displaystyle
R(G;p)=(p)^{|E(G)-|V(G)|+k(G)}(1-p)^{|V(G)|-k(G)}T(G;1,\frac{1}{p})$

Hence we get:

######  Proposition 7.12.

$Fl<_{s.d.p}T$ and $R<_{s.d.p}T$ .

##  8\. Conclusion

We have shown that many graph polynomials are weakly distinguishing on all
proper minor closed addable graph properties, including many interesting
properties such as planar graphs, graphs with tree-width at most $k$, and
$K_{k}$ free graphs (for $4<k\in\mathbb{N}$). In addition, we proved that the
Domination, Characteristic, and the edge elimination polynomial $\xi(G;x,y,z)$
are weakly distinguishing on the properties of graphs with genus less then $k$
for all $k\in\mathbb{N}$. This also applies to graph polynomials derivable
from $\xi$, such as the generalized chromatic polynomial, Tutte polynomial and
its variants, the matching, the independence, and the clique polynomials.

Our results relied on the fact that proper minor closed addable properties
are, in a sense, small, and so they do not settle the question whether the
Domination, Characteristic or Tutte polynomials are weakly distinguishing,
almost complete, or otherwise on all graphs.

We have shown that for the above graph polynomials $P$, the sequence
$\alpha_{P}^{\mathcal{C}}(n)=\frac{|U_{P}^{\mathcal{C}}(n)|}{|\mathcal{C}(n)|}$
tends to $0$ as $n$ tends to infinity.

The following questions are natural extensions of the work in this paper:

######  Problem 8.1.

What can be said about $\alpha_{P}^{\mathcal{C}}(n)$ when $\mathcal{C}$ is
assumed to be a hereditary or monotone graph property?

######  Problem 8.2.

Can we find a graph polynomial $P$ and a graph property $\mathcal{C}$ such
that we can prove that $\alpha_{P}^{\mathcal{C}}(n)\geq\beta$ for all
sufficiently large $n$ for some fixed $\beta\in(0,1]$?

######  Problem 8.3.

For $P$ one of the above polynomials and $\mathcal{A}$ a proper minor closed
addable property, select a random graph $G_{n}$ uniformly at random in
$\mathcal{A}_{n}$, and denote $[G_{n}]=\\{H\in\mathcal{A}_{n}:P(G)=P(H)\\}$.
What can be said about the limit distribution of the random variable
$|[G_{n}]|$?

## References

  * [1] Martin Aigner.  A course in enumeration.  Springer, 2007.
  * [2] Saeid Alikhani and Yee-hock Peng.  Introduction to domination polynomial of a graph.  arXiv preprint arXiv:0905.2251, 2009.
  * [3] Ilia Averbouch, Benny Godlin, and Johann A Makowsky.  A most general edge elimination polynomial.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 31–42. Springer, 2008.
  * [4] Ilia Averbouch, Benny Godlin, and Johann A. Makowsky.  An extension of the bivariate chromatic polynomial.  European Journal of Combinatorics, 31:1–17, 2010.
  * [5] Béla Bollobás, Luke Pebody, and Oliver Riordan.  Contraction–deletion invariants for graphs.  Journal of Combinatorial Theory, Series B, 80(2):320–345, 2000\.
  * [6] Andries E Brouwer and Willem H Haemers.  Spectra of graphs.  Springer Science & Business Media, 2011.
  * [7] Frank H Clarke.  The Characteristic Polynomial of a Graph.  PhD thesis, McGill University Libraries, 1970.
  * [8] K. Dohmen, A. Pönitz, and P. Tittmann.  A new two-variable generalization of the chromatic polynomial.  Theoretical Computer Science, pages 69–90, 2003.
  * [9] Edward J Farrell.  An introduction to matching polynomials.  Journal of Combinatorial Theory, Series B, 27(1):75–86, 1979.
  * [10] Chris D Godsil and Ivan Gutman.  On the theory of the matching polynomial.  Journal of Graph Theory, 5(2):137–144, 1981.
  * [11] Ivan Gutman.  A survey on the matching polynomial.  Graph Polynomials, pages 73–95, 2016.
  * [12] Tomer Kotek, James Preen, Frank Simon, Peter Tittmann, and Martin Trinks.  Recurrence relations and splitting formulas for the domination polynomial.  arXiv preprint arXiv:1206.5926, 2012.
  * [13] Sergei K Lando and Alexander K Zvonkin.  Graphs on surfaces and their applications, volume 141.  Springer Science & Business Media, 2013.
  * [14] László Lovász.  Graph minor theory.  Bulletin of the American Mathematical Society, 43(1):75–86, 2006\.
  * [15] Johann A Makowsky and Vsevolod Rakita.  On weakly distinguishing graph polynomials.  Discrete Mathematics & Theoretical Computer Science, 21, 2019.
  * [16] Johann A. Makowsky, Elena V. Ravve, and Tomer Kotek.  A logician’s view of graph polynomials.  Annals of Pure and Applied Logic, 170(9):1030–1069, 2019.
  * [17] Johann A. Makowsky and Ruixue Zhang.  On p-unique hypergraphs.  arXiv preprint arXiv:1712.07357, 2017.
  * [18] Colin McDiarmid.  Random graphs on surfaces.  Journal of Combinatorial Theory, Series B, 98(4):778–797, 2008\.
  * [19] Colin Mcdiarmid.  Random graphs from a minor-closed class.  Combinatorics, Probability and Computing, 18(4):583–599, 2009.
  * [20] Colin McDiarmid, Angelika Steger, and Dominic JA Welsh.  Random planar graphs.  Journal of Combinatorial Theory, Series B, 93(2):187–205, 2005\.
  * [21] Bojan Mohar, Y Alavi, G Chartrand, and OR Oellermann.  The laplacian spectrum of graphs.  Graph theory, combinatorics, and applications, 2(871-898):12, 1991\.
  * [22] Bojan Mohar and Carsten Thomassen.  Graphs on surfaces, volume 10.  JHU Press, 2001.
  * [23] Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan.  Proper minor-closed families are small.  Journal of Combinatorial Theory, Series B, 96(5):754–757, 2006\.
  * [24] Marc Noy.  Graphs determined by polynomial invariants.  Theoretical Computer Science, 307(2):365–384, 2003.
  * [25] Allen J Schwenk.  Almost all trees are cospectral.  New directions in the theory of graphs, pages 275–307, 1973.
  * [26] Martin Trinks.  The covered components polynomial: A new representation of the edge elimination polynomial.  arXiv preprint arXiv:1103.2218, 2011.