# Lower Bounds and properties for the average number of colors in the non-
equivalent colorings of a graph

Alain Hertz1, Hadrien Mélot2, Sébastien Bonte2, Gauvain Devillez2,
1 Department of Mathematics and Industrial Engineering
Polytechnique Montréal - Gerad, Montréal, Canada
Corresponding author. Email<EMAIL_ADDRESS>
2 Computer Science Department - Algorithms Lab
University of Mons, Mons, Belgium

Abstract.
We study the average number $\mathcal{A}(G)$ of colors in the non-equivalent
colorings of a graph $G$. We show some general properties of this graph
invariant and determine its value for some classes of graphs. We then
conjecture several lower bounds on $\mathcal{A}(G)$ and prove that these
conjectures are true for specific classes of graphs such as triangulated
graphs and graphs with maximum degree at most 2.

_Keywords:_ graph coloring, average number of colors, graphical Bell numbers.

##  1 Introduction

A coloring of a graph $G$ is an assignment of colors to its vertices such that
adjacent vertices have different colors. The chromatic number $\chi(G)$ is the
minimum number of colors in a coloring of $G$. The total number
$\mathcal{B}(G)$ of non-equivalent colorings (i.e., with different partitions
into color classes) of a graph $G$ is the number of partitions of the vertex
set of $G$ whose blocks are stable sets (i.e., sets of pairwise non-adjacent
vertices). This invariant has been studied by several authors in the last few
years [1, 7, 8, 9, 11, 12] under the name of (graphical) Bell number.

Recently, Hertz et _a_ l. have defined a new graph invariant $\mathcal{A}(G)$
which is equal to the average number of colors in the non-equivalent colorings
of a graph $G$. It can be seen as a generalization of a concept linked to Bell
numbers. More precisely, the Bell numbers $({\sf B}_{n})_{n\geq 0}$ count the
number of different ways to partition a set that has exactly $n$ elements. The
2-Bell numbers $({\sf T}_{n})_{n\geq 0}$ count the total number of blocks in
all partitions of a set of $n$ elements. Odlyzko and Richmond [14] have
studied the average number ${\sf A}_{n}$ of blocks in a partition of a set of
$n$ elements, which can be defined as ${\sf A}_{n}=\frac{{\sf T}_{n}}{{\sf
B}_{n}}.$ The graph invariant $\mathcal{A}(G)$ that we study in this paper
generalizes ${\sf A}_{n}$. Indeed, when constraints (represented by edges in
$G$) impose that certain pairs of elements (represented by vertices) cannot
belong to the same block of a partition, $\mathcal{A}(G)$ is the average
number of blocks in the partitions that respect all constraints. Hence, for a
graph of order $n$, $\mathcal{A}(G)={\sf A}_{n}$ if $G$ is the empty graph of
order $n$.

As shown in [10], $\mathcal{A}(G)$ can help discover nontrivial inequalities
for the Bell numbers. For example, we will see that $\mathcal{A}({\sf
P}_{n})=\frac{{\sf B}_{n}}{{\sf B}_{n-1}}$ and $\mathcal{A}({\sf
P}_{n})<\mathcal{A}({\sf P}_{n+1})$ for $n\geq 1$, where ${\sf P}_{n}$ is the
path on $n$ vertices. This immediately implies ${\sf B}_{n}^{2}<{\sf
B}_{n-1}{\sf B}_{n+1}$, which means that the sequence $({\sf B}_{n})_{n\geq
0}$ is strictly log-convex. This result has also been proved recently by Alzer
[2] using numerical arguments.

The best possible upper bound for $\mathcal{A}(G)$ is clearly the order $n$ of
$G$ since all colorings of $G$ use at most $n$ colors and $\mathcal{A}({\sf
K}_{n})=n$ for the clique ${\sf K}_{n}$ of order $n$. It seems however much
more complex to define a lower bound for $\mathcal{A}(G)$, as a function of
$n$, which is reached by at least one graph of order $n$. We think that the
best possible lower bound is $\frac{{\sf B}_{n+1}-{\sf B}_{n}}{{\sf B}_{n}}$
and is reached by the empty graph of order $n$. But it is just a conjecture we
are trying to prove.

In the next section we fix some notations, while Section 3 is devoted to basic
properties of $\mathcal{A}(G)$. In Section 4, we give values of
$\mathcal{A}(G)$ for some particular graphs $G$ that we will deal with later.
We then state in Section 5 three conjectures on a lower bound for
$\mathcal{A}(G)$ and prove that they are true for graphs $G$ with maximum
degree $\Delta(G)\leq 2$ and for triangulated graphs.

##  2 Notation

For basic notions of graph theory that are not defined here, we refer to
Diestel [4]. Let $G=(V,E)$ be a simple undirected graph. The _order_ $n=|V|$
of $G$ is its number of vertices and the _size_ $m=|E|$ of $G$ is its number
of edges. We write $G\simeq H$ if $G$ and $H$ are two isomorphic graphs, and
$\overline{G}$ is the complement of $G$. We denote by ${\sf K}_{n}$ (resp.
${\sf C}_{n}$, ${\sf P}_{n}$ and $\overline{{\sf K}}_{n}$) the _complete
graph_ (resp. the _cycle_ , the _path_ and the empty graph) of order $n$. We
write ${\sf K}_{a,b}$ for the complete bipartite graph where $a$ and $b$ are
the cardinalities of the two sets of vertices of the bipartition. For a subset
$S$ of vertices in a graph $G$, we write $G[S]$ for the subgraph of $G$
induced by $S$.

Let $N(v)$ be the set of neighbors of a vertex $v$ in $G$. A vertex $v$ is
_isolated_ if $|N(v)|=0$ and is _dominant_ if $|N(v)|=n-1$ (where $n$ is the
order of $G$). We write $\Delta(G)$ for the _maximum degree_ of $G$. A vertex
$v$ of a graph $G$ is _simplicial_ if the induced subgraph $G[N(v)]$ of $G$ is
a clique. A graph is _triangulated_ if each of its induced subgraphs contains
a simplicial vertex.

Let $u$ and $v$ be two vertices in a graph $G$ of order $n$, We use the
following notations:

  * •

$G_{\mid uv}$ is the graph (of order $n-1$) obtained from $G$ by identifying
(merging) the vertices $u$ and $v$ and, if $uv\in E(G)$, by removing the edge
$uv$;

  * •

if $uv\in E(G)$, $G-uv$ is the graph obtained by removing the edge $uv$ from
$G$;

  * •

if $uv\notin E(G)$, $G+uv$ is the graph obtained by adding the edge $uv$ in
$G$;

  * •

$G-v$ is the graph obtained from $G$ by removing $v$ and all its incident
edges.

Given two graphs $G_{1}$ and $G_{2}$ (with disjoint sets of vertices), we
write $G_{1}\cup G_{2}$ for the _disjoint union_ of $G_{1}$ and $G_{2}$, while
the _join_ $G_{1}+G_{2}$ of $G_{1}$ and $G_{2}$ is the graph obtained from
$G_{1}\cup G_{2}$ by adding all possible edges between the vertices of $G_{1}$
and those of $G_{2}$. Also, $G\cup p{\sf K}_{1}$ is the graph obtained from
$G$ by adding $p$ isolated vertices.

A _coloring_ of a graph $G$ is an assignment of colors to the vertices of $G$
such that adjacent vertices have different colors. The _chromatic number_
$\chi(G)$ of $G$ is the minimum number of colors in a coloring of $G$. Two
colorings are _equivalent_ if they induce the same partition of the vertex set
into color classes. Let $S(G,k)$ be the number of non-equivalent colorings of
a graph $G$ that use _exactly_ $k$ colors. Then, the total number
$\mathcal{B}(G)$ of non-equivalent colorings of a graph $G$ is defined by

$\mathcal{B}(G)=\sum_{k=1}^{n}S(G,k)=\sum_{k=\chi(G)}^{n}S(G,k),$

and the total number $\mathcal{T}(G)$ of color classes in the non-equivalent
colorings of a graph $G$ is defined by

$\mathcal{T}(G)=\sum_{k=1}^{n}kS(G,k)=\sum_{k=\chi(G)}^{n}kS(G,k).$

The average number $\mathcal{A}(G)$ of colors in the non-equivalent colorings
of a graph $G$ can therefore be defined as

$\mathcal{A}(G)=\frac{\mathcal{T}(G)}{\mathcal{B}(G)}.$

Note that $\mathcal{B}(\overline{{\sf K}}_{n})={\sf
B}_{n},\mathcal{T}(\overline{{\sf K}}_{n})={\sf T}_{n}$, and
$\mathcal{A}(\overline{{\sf K}}_{n})={\sf A}_{n}$. As another example,
consider the complement $\overline{{\sf P}}_{5}$ of a path on 5 vertices. As
shown in Figure 1, there are three non-equivalent colorings of $\overline{{\sf
P}}_{5}$ with 3 colors, four with 4 colors, and one with 5 colors, which gives
$\mathcal{B}(\overline{{\sf P}}_{5})=8$, $\mathcal{T}(\overline{{\sf
P}}_{5})=30$ and $\mathcal{A}(\overline{{\sf P}}_{5})=\frac{30}{8}=3.75.$

Figure 1: The non-equivalent colorings of $\overline{{\sf P}}_{5}$.

##  3 Basic properties of $\mathcal{A}(G)$

As for several other invariants in graph coloring, the _deletion-contraction_
rule (also often called the Fundamental Reduction Theorem [6]) can be used to
compute $\mathcal{B}(G)$ and $\mathcal{T}(G)$. More precisely, let $u$ and $v$
be any pair of distinct vertices of $G$. As shown in [8, 12], we have

$\displaystyle S(G,k)=S(G-uv,k)-S(G_{\mid uv},k)$ $\displaystyle\quad\forall
uv\in E(G),$ (1) $\displaystyle S(G,k)=S(G+uv,k)+S(G_{\mid uv},k)$
$\displaystyle\quad\forall uv\notin E(G).$ (2)

It follows that

$\displaystyle\left.\begin{array}[]{ll}\mathcal{B}(G)=\mathcal{B}(G-uv)-\mathcal{B}(G_{\mid
uv})\\\ \mathcal{T}(G)=\mathcal{T}(G-uv)-\mathcal{T}(G_{\mid
uv})\end{array}\right\\}$ $\displaystyle\quad\forall uv\in E(G),$ (5)
$\displaystyle\left.\begin{array}[]{ll}\mathcal{B}(G)=\mathcal{B}(G+uv)+\mathcal{B}(G_{\mid
uv})\\\ \mathcal{T}(G)=\mathcal{T}(G+uv)+\mathcal{T}(G_{\mid
uv})\end{array}\right\\}$ $\displaystyle\quad\forall uv\notin E(G).$ (8)

######  Theorem 1.

Given any two graphs $G_{1}$ and $G_{2}$, we have

$\mathcal{A}(G_{1}+G_{2})=\mathcal{A}(G_{1})+\mathcal{A}(G_{2}).$

###### Proof.

As observed in [1], given any coloring of $G_{1}+G_{2}$, none of the vertices
of $G_{1}$ can share a color with a vertex of $G_{2}$, which immediately gives
$\mathcal{B}(G_{1}+G_{2})=\mathcal{B}(G_{1})\mathcal{B}(G_{2})$. For
$\mathcal{T}(G_{1}+G_{2})$, assuming that $G_{1}$ and $G_{2}$ are of order
$n_{1}$ and $n_{2}$, respectively, we get

$\displaystyle\mathcal{T}(G_{1}+G_{2})$
$\displaystyle=\sum_{k=1}^{n_{1}}\sum_{k^{\prime}=1}^{n_{2}}(k+k^{\prime})S(G_{1},k)S(G_{2},k^{\prime})=\sum_{k=1}^{n_{1}}S(G_{1},k)\sum_{k^{\prime}=1}^{n_{2}}(k+k^{\prime})S(G_{2},k^{\prime})$
$\displaystyle=\sum_{k=1}^{n_{1}}S(G_{1},k)\left(k\sum_{k^{\prime}=1}^{n_{2}}S(G_{2},k^{\prime})+\sum_{k^{\prime}=1}^{n_{2}}k^{\prime}S(G_{2},k^{\prime})\right)$
$\displaystyle=\sum_{k=1}^{n_{1}}kS(G_{1},k)\sum_{k^{\prime}=1}^{n_{2}}S(G_{2},k^{\prime})+\sum_{k=1}^{n_{1}}S(G_{1},k)\sum_{k^{\prime}=1}^{n_{2}}k^{\prime}S(G_{2},k^{\prime})$
$\displaystyle=\mathcal{T}(G_{1})\mathcal{B}(G_{2})+\mathcal{B}(G_{1})\mathcal{T}(G_{2}).$

Hence,

$\displaystyle\mathcal{A}(G_{1}+G_{2})$
$\displaystyle=\frac{\mathcal{T}(G_{1}+G_{2})}{\mathcal{B}(G_{1}+G_{2})}=\frac{\mathcal{T}(G_{1})\mathcal{B}(G_{2})+\mathcal{B}(G_{1})\mathcal{T}(G_{2})}{\mathcal{B}(G_{1})\mathcal{B}(G_{2})}$
$\displaystyle=\frac{\mathcal{T}(G_{1})}{\mathcal{B}(G_{1})}+\frac{\mathcal{T}(G_{2})}{\mathcal{B}(G_{2})}=\mathcal{A}(G_{1})+\mathcal{A}(G_{2}).$

∎

The following Corollary is also proved in [10].

######  Corollary 2.

If $v$ is a dominant vertex of a graph $G$, then,

$\mathcal{A}(G)=\mathcal{A}(G-v)+1.$

###### Proof.

If $v$ is a dominant vertex of a graph $G$, then $G\simeq(G-v)+{\sf K}_{1}$,
and since $\mathcal{A}({\sf K}_{1})=1$, Theorem 1 gives
$\mathcal{A}(G)=\mathcal{A}(G-v)+1$. ∎

In the following, given a subset $W$ of vertices in a graph $G$, we denote by
$S_{W,i}(G,k)$ the number of non-equivalent colorings of $G$ that use exactly
$k$ colors, and where exactly $i$ of them appear on $W$. Hence,
$S(G,k)=\sum_{i=0}^{|W|}S_{W,i}(G,k)$.

######  Lemma 3.

Let $v$ be a vertex in a graph $G$ of order $n$ and let $N(v)$ be its set of
neighbors in $G$. Then

  * •

$\displaystyle\mathcal{B}(G)=\mathcal{B}(G-v)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k-i)S_{N(v),i}(G-v,k)$,
and

  * •

$\displaystyle\mathcal{T}(G)=\mathcal{T}(G-v)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k(k-i)+1)S_{N(v),i}(G-v,k)$.

###### Proof.

Since $S_{N(v),i}(G,k)=S_{N(v),i}(G-v,k-1)+(k-i)S_{N(v),i}(G-v,k)$, we have

$\displaystyle\mathcal{B}(G)$
$\displaystyle=\sum_{k=1}^{n}S(G,k)=\sum_{k=1}^{n}\sum_{i=0}^{|N(v)|}S_{N(v),i}(G,k)$
$\displaystyle=\sum_{k=1}^{n}\sum_{i=0}^{|N(v)|}S_{N(v),i}(G-v,k-1)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k-i)S_{N(v),i}(G-v,k)$
$\displaystyle=\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}S_{N(v),i}(G-v,k)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k-i)S_{N(v),i}(G-v,k)$
$\displaystyle=\mathcal{B}(G-v)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k-i)S_{N(v),i}(G-v,k)$

and

$\displaystyle\mathcal{T}(G)$
$\displaystyle=\sum_{k=1}^{n}kS(G,k)=\sum_{k=1}^{n}\sum_{i=0}^{|N(v)|}kS_{N(v),i}(G,k)$
$\displaystyle=\sum_{k=1}^{n}\sum_{i=0}^{|N(v)|}kS_{N(v),i}(G-v,k-1)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}k(k-i)S_{N(v),i}(G-v,k)$
$\displaystyle=\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k+1)S_{N(v),i}(G-v,k)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}k(k-i)S_{N(v),i}(G-v,k)$
$\displaystyle=\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}kS_{N(v),i}(G-v,k)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k(k-i)+1)S_{N(v),i}(G-v,k)$
$\displaystyle=\mathcal{T}(G-v)+\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k(k-i)+1)S_{N(v),i}(G-v,k).\qed$

######  Theorem 4.

Let $v$ be a vertex in a graph $G$. If $\chi(G[N(v)])\geq|N(v)|-3$ then
$\mathcal{A}(G)>\mathcal{A}(G-v)$.

###### Proof.

Let $n$ be the order of $G$. We know from Lemma 3 that

$\displaystyle\mathcal{A}(G)-\mathcal{A}(G-v)=\frac{\mathcal{T}(G-v)+a}{\mathcal{B}(G-v)+b}-\frac{\mathcal{T}(G-v)}{\mathcal{B}(G-v)}=\frac{a\mathcal{B}(G-v)-b\mathcal{T}(G-v)}{\mathcal{B}(G)\mathcal{B}(G-v)}$

where $\displaystyle
a=\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k(k-i)+1)S_{N(v),i}(G-v,k)$ and
$\displaystyle b=\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}(k-i)S_{N(v),i}(G-v,k)$.

It suffices to show that $a\mathcal{B}(G{-}v){-}b\mathcal{T}(G{-}v)>0$. Let
$\mathcal{P}$ be the set of pairs $(k,i)$ such that $S_{N(v),i}(G-v,k){>}0$.
Since $\chi(G[N(v)])\geq|N(v)|-3$, we have $k\geq i\geq|N(v)|-3$ for all
$(k,i)\in\mathcal{P}$. For two pairs $(k,i)$ and $(k^{\prime},i^{\prime})$ in
$\mathcal{P}$, we write $(k,i){>}(k^{\prime},i^{\prime})$ if $k{>}k^{\prime}$
or $k{=}k^{\prime}$ and $i{>}i^{\prime}$. Also, let
$f(k,k^{\prime},i,i^{\prime})=S_{N(v),i}(G{-}v,k)S_{N(v),i^{\prime}}(G{-}v,k^{\prime})$.
We have

$\displaystyle\quad a\mathcal{B}(G{-}v)-b\mathcal{T}(G{-}v)$ $\displaystyle=$
$\displaystyle\quad
a\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}S_{N(v),i}(G-v,k)-b\sum_{k=1}^{n-1}\sum_{i=0}^{|N(v)|}kS_{N(v),i}(G-v,k)$
$\displaystyle=$
$\displaystyle\sum_{(k,i)\in\mathcal{P}}S_{N(v),i}(G-v,k)^{2}\Bigl{(}{(k(k-i)+1)-(k-i)k}\Bigr{)}$
$\displaystyle\quad+\sum_{(k,i)>(k^{\prime},i^{\prime})}f(k,k^{\prime},i,i^{\prime})\Bigl{(}{(k(k{-}i){+}1){+}(k^{\prime}(k^{\prime}{-}i^{\prime}){+}1){-}(k{-}i)k^{\prime}{-}(k^{\prime}{-}i^{\prime})k}\Bigr{)}$
$\displaystyle=$
$\displaystyle\quad\sum_{(k,i)\in\mathcal{P}}S_{N(v),i}(G{-}v,k)^{2}{+}\sum_{(k,i){>}(k^{\prime},i^{\prime})}f(k,k^{\prime},i,i^{\prime})\Bigl{(}{(k{-}k^{\prime})^{2}{-}(k{-}k^{\prime})(i{-}i^{\prime}){+}2}\Bigr{)}.$

Note that $\mathcal{P}\neq\emptyset$ since $S_{N(v),|N(v)|}(G-v,n-1)=1$.
Hence, $\sum_{(k,i)\in\mathcal{P}}S_{N(v),i}(G-v,k)^{2}{>}0$, and it is
sufficient to prove that
$(k-k^{\prime})^{2}-(k-k^{\prime})(i-i^{\prime})+2\geq 0$ for every two pairs
$(k,i)$ and $(k^{\prime},i^{\prime})$ in $\mathcal{P}$ with
$(k,i){>}(k^{\prime},i^{\prime})$. For two such pairs $(k,i)$ and
$(k^{\prime},i^{\prime})$, we have $i-i^{\prime}\leq|N(v)|-(|N(v)|-3)=3$.
Hence,

  * •

if $k=k^{\prime}$, then
$(k-k^{\prime})^{2}-(k-k^{\prime})(i-i^{\prime})+2=2>0$;

  * •

if $k=k^{\prime}+1$, then
$(k-k^{\prime})^{2}-(k-k^{\prime})(i-i^{\prime})+2=3-(i-i^{\prime})\geq 0$;

  * •

if $k=k^{\prime}+2$, then
$(k-k^{\prime})^{2}-(k-k^{\prime})(i-i^{\prime})+2=6-2(i-i^{\prime})\geq 0$;

  * •

if $k\geq k^{\prime}+3$, then
$(k-k^{\prime})^{2}-(k-k^{\prime})(i-i^{\prime})+2\geq 2$.∎

######  Corollary 5.

If $v$ is a vertex of degree at most 4 in a graph $G$, then
$\mathcal{A}(G)>\mathcal{A}(G-v)$.

###### Proof.

Since $|N(v)|\leq 4$, we have:

  * •

if $N(v)=\emptyset$, then $\chi(G[N(v)])=0>-3=|N(v)|-3$;

  * •

if $N(v)\neq\emptyset$, then $\chi(G[N(v)])\geq 1\geq|N(v)|-3$.

In both cases, we conclude from Theorem 4 that
$\mathcal{A}(G)>\mathcal{A}(G-v)$.

∎

######  Corollary 6.

Let $v$ be a simplicial vertex in a graph $G$. Then
$\mathcal{A}(G)>\mathcal{A}(G-v)$.

###### Proof.

Since $v$ is simplicial in $G$, we have $\chi(G[N(v)])=|N(v)|>|N(v)|-3$.
Hence, we conclude from Theorem 4 that $\mathcal{A}(G)>\mathcal{A}(G-v)$.

∎

######  Theorem 7.

Let $v$ be a simplicial vertex of degree at least one in a graph $G$ of order
$n$, and let $w$ be one of its neighbors in $G$. Then
$\mathcal{A}(G)>\mathcal{A}(G-vw)$.

###### Proof.

Let $H=(G-v)\cup{\sf K}_{1}$. In other words, $H$ is obtained from $G-v$ by
adding an isolated vertex. It follows from Lemma 3 that

$\displaystyle\mathcal{B}(H)$
$\displaystyle=\mathcal{B}(G-v)+\sum_{k=1}^{n-1}\sum_{i=0}^{0}(k-i)S_{\emptyset,i}(G-v,k)$
$\displaystyle=\mathcal{B}(G-v)+\sum_{k=1}^{n-1}kS(G-v,k)$

and

$\displaystyle\mathcal{T}(H)$
$\displaystyle=\mathcal{T}(G-v)+\sum_{k=1}^{n-1}\sum_{i=0}^{0}(k(k-i)+1)S_{\emptyset,i}(G-v,k)$
$\displaystyle=\mathcal{T}(G-v)+\sum_{k=1}^{n-1}(k^{2}+1)S(G-v,k).$

Also, since $S_{N(v),i}(G{-}v,k){=}0$ for $i\neq|N(v)|$, we have
$S(G{-}v,k){=}S_{N(v),|N(v)|}(G{-}v,k)$ and it follows from Lemma 3 that

$\displaystyle\mathcal{B}(G)$
$\displaystyle=\mathcal{B}(G-v)+\sum_{k=1}^{n-1}(k-|N(v)|)S(G-v,k)$
$\displaystyle=\Big{(}\mathcal{B}(G-v)+\sum_{k=1}^{n-1}kS(G-v,k)\Big{)}-|N(v)|\sum_{k=1}^{n-1}S(G-v,k)$
$\displaystyle=\mathcal{B}(H)-|N(v)|\mathcal{B}(G-v)$

and

$\displaystyle\mathcal{T}(G)$
$\displaystyle=\mathcal{T}(G-v)+\sum_{k=1}^{n-1}\Big{(}k(k-|N(v)|)+1\Big{)}S(G-v,k)$
$\displaystyle=\Big{(}\mathcal{T}(G-v)+\sum_{k=1}^{n-1}(k^{2}+1)S(G-v,k)\Big{)}-|N(v)|\sum_{k=1}^{n-1}kS(G-v,k)$
$\displaystyle=\mathcal{T}(H)-|N(v)|\mathcal{T}(G-v).$

Similarly, since $v$ is simplicial (of degree $|N(v)|-1$) in $G-vw$, we have

$\mathcal{B}(G-vw)=\mathcal{B}(H)-(|N(v)|-1)\mathcal{B}(G-v)$

and

$\mathcal{T}(G-vw)=\mathcal{T}(H)-(|N(v)|-1)\mathcal{T}(G-v).$

Hence,

$\displaystyle\mathcal{A}(G)-\mathcal{A}(G-vw)$
$\displaystyle=\frac{\mathcal{T}(G)}{\mathcal{B}(G)}-\frac{\mathcal{T}(G-vw)}{\mathcal{B}(G-vw)}$
$\displaystyle=\frac{\mathcal{T}(H){-}|N(v)|\mathcal{T}(G{-}v)}{\mathcal{B}(H){-}|N(v)|\mathcal{B}(G{-}v)}{-}\frac{\mathcal{T}(H){-}(|N(v)|{-}1)\mathcal{T}(G{-}v)}{\mathcal{B}(H){-}(|N(v)|{-}1)\mathcal{B}(G{-}v)}$
$\displaystyle=\frac{\mathcal{T}(H)\mathcal{B}(G{-}v){-}\mathcal{B}(H)\mathcal{T}(G{-}v)}{\mathcal{B}(G)\mathcal{B}(G{-}vw)}.$

Since $v$ is isolated in $H$, it is simplicial and we know from Corollary 6
that

$\displaystyle\mathcal{A}(H)>\mathcal{A}(G-v)$
$\displaystyle\iff\frac{\mathcal{T}(H)}{\mathcal{B}(H)}>\frac{\mathcal{T}(G-v)}{\mathcal{B}(G-v)}$
$\displaystyle\iff\mathcal{T}(H)\mathcal{B}(G-v)-\mathcal{B}(H)\mathcal{T}(G-v)>0$

which implies $\mathcal{A}(G)-\mathcal{A}(G-vw)>0$.

∎

######  Lemma 8.

Let $G$ and $H$ be two graphs and suppose $H$ has order $n$. Then

  * •

$\mathcal{B}(G\cup H)=\displaystyle\sum_{k=1}^{n}S(H,k)\mathcal{B}(G\cup{\sf
K}_{k})$, and

  * •

$\mathcal{T}(G\cup H)=\displaystyle\sum_{k=1}^{n}S(H,k)\mathcal{T}(G\cup{\sf
K}_{k})$.

###### Proof.

We first prove that $\mathcal{B}(G\cup
H)=\sum_{k=1}^{n}S(H,k)\mathcal{B}(G\cup{\sf K}_{k})$ for all graphs $H$ of
order $n$. For $n=1$, we have $H={\sf K}_{1}$, and since $S({\sf K}_{1},1)=1$,
we have $\mathcal{B}(G\cup{\sf K}_{1})=\sum_{k=1}^{1}S({\sf
K}_{1},k)\mathcal{B}(G\cup{\sf K}_{1})$. For larger values of $n$ we proceed
by double induction on the order $n$ and the size $m$ of $H$. So assume $H$
has order $n$ and size $m$.

  * •

If $m=\frac{n(n-1)}{2}$, then $H={\sf K}_{n}$. Since $S({\sf K}_{n},i)=0$ for
$i=1,\ldots,n-1$ and $S({\sf K}_{n},n)=1$, we have $\mathcal{B}(G\cup{\sf
K}_{n})=\sum_{k=1}^{n}S({\sf K}_{n},k)\mathcal{B}(G\cup{\sf K}_{n})$.

  * •

If $m<\frac{n(n-1)}{2}$, then $H$ contains two non-adjacent vertices $u$ and
$v$ and we know from Equations (8) that $\mathcal{B}(G\cup
H)=\mathcal{B}(G\cup(H+uv))+\mathcal{B}(G\cup H_{\mid uv})$. Since
$G\cup(H+uv)$ has order $n$ and size $m+1$ and $G\cup(H_{\mid uv})$ has order
$n-1$, we know by induction that

$\displaystyle\mathcal{B}(G\cup H)$
$\displaystyle=\sum_{k=1}^{n}S(H+uv,k)\mathcal{B}(G\cup{\sf
K}_{k})+\sum_{k=1}^{n-1}S(H_{\mid uv},k)\mathcal{B}(G\cup{\sf K}_{k})$
$\displaystyle=\sum_{k=1}^{n}\bigl{(}S(H+uv,k)+S(H_{\mid
uv},k)\bigr{)}\mathcal{B}(G\cup{\sf K}_{k})$
$\displaystyle=\sum_{k=1}^{n}S(H,k)\mathcal{B}(G\cup{\sf K}_{k}).$

The proof for $\mathcal{T}(G\cup H)$ is similar.

∎

######  Theorem 9.

Let $H_{1},H_{2}$ be any two graphs. If $S(H_{1},k)S(H_{2},k^{\prime})\geq
S(H_{2},k)S(H_{1},k^{\prime})$ for all $k{>}k^{\prime}$, the inequality being
strict for at least one pair $(k,k^{\prime})$, then ${\mathcal{A}(G\cup
H_{1})>\mathcal{A}(G\cup H_{2})}$ for all graphs $G$.

###### Proof.

Let
$f(k,k^{\prime}){=}S(H_{1},k)S(H_{2},k^{\prime}){-}S(H_{2},k)S(H_{1},k^{\prime})$
and assume that $H_{1}$ and $H_{2}$ are of order $n_{1}$ and $n_{2}$,
respectively. Note that $n_{1}\geq n_{2}$ else we would have $n_{2}>n_{1}$ and
$f(n_{2},n_{1}){=}S(H_{1},n_{2})S(H_{2},n_{1}){-}S(H_{2},n_{2})S(H_{1},n_{1})=-1<0$.
We know from Lemma 8 that

$\displaystyle\mathcal{A}(G\cup H_{1}){-}\mathcal{A}(G\cup H_{2})$
$\displaystyle=\frac{\displaystyle\sum_{k=1}^{n_{1}}S(H_{1},k)\mathcal{T}(G\cup{\sf
K}_{k})}{\displaystyle\sum_{k=1}^{n_{1}}S(H_{1},k)\mathcal{B}(G\cup{\sf
K}_{k})}-\frac{\displaystyle\sum_{k=1}^{n_{2}}S(H_{2},k)\mathcal{T}(G\cup{\sf
K}_{k})}{\displaystyle\sum_{k=1}^{n_{2}}S(H_{2},k)\mathcal{B}(G\cup{\sf
K}_{k})}$
$\displaystyle=\frac{\displaystyle\sum_{k=1}^{n_{1}}\sum_{k^{\prime}=1}^{n_{1}}f(k,k^{\prime})\mathcal{T}(G{\cup}{\sf
K}_{k})\mathcal{B}(G{\cup}{\sf K}_{k^{\prime}})}{\mathcal{B}(G\cup
H_{1})\mathcal{B}(G\cup H_{2})}.$

Since $f(k,k)=0$ for all $k$ and $f(k,k^{\prime})=-f(k^{\prime},k)$ for all
$k\neq k^{\prime}$, we deduce

$\displaystyle\mathcal{A}(G\cup H_{1}){-}\mathcal{A}(G\cup H_{2})$
$\displaystyle=\frac{\displaystyle\sum_{k^{\prime}=1}^{n_{1}-1}\sum_{k=k^{\prime}{+}1}^{n_{1}}f(k,k^{\prime})\Bigl{(}\mathcal{T}(G{\cup}{\sf
K}_{k})\mathcal{B}(G{\cup}{\sf K}_{k^{\prime}}){-}\mathcal{T}(G{\cup}{\sf
K}_{k^{\prime}})\mathcal{B}(G{\cup}{\sf K}_{k})\Bigr{)}}{\mathcal{B}(G\cup
H_{1})\mathcal{B}(G\cup H_{2})}.$

Note that if $k>k^{\prime}$, then $G\cup{\sf K}_{k}$ is obtained from
$G\cup{\sf K}_{k^{\prime}}$ by repeatedly adding a simplicial vertex. Hence,
we know from Corollary 6 that

$\displaystyle\mathcal{A}(G\cup{\sf K}_{k})>\mathcal{A}(G\cup{\sf
K}_{k^{\prime}})$ $\displaystyle\iff\frac{\mathcal{T}(G\cup{\sf
K}_{k})}{\mathcal{B}(G\cup{\sf K}_{k})}>\frac{\mathcal{T}(G\cup{\sf
K}_{k^{\prime}})}{\mathcal{B}(G\cup{\sf K}_{k^{\prime}})}$
$\displaystyle\iff\mathcal{T}(G\cup{\sf K}_{k})\mathcal{B}(G\cup{\sf
K}_{k^{\prime}})-\mathcal{T}(G\cup{\sf K}_{k^{\prime}})\mathcal{B}(G\cup{\sf
K}_{k})>0.$

Since
$f(k,k^{\prime})=S(H_{1},k)S(H_{2},k^{\prime})-S(H_{1},k^{\prime})S(H_{2},k)$
is positive for all $(k,k^{\prime})$, and strictly positive for at least one
such pair, we have $\mathcal{A}(G\cup H_{1})-\mathcal{A}(G\cup H_{2})>0$.

∎

As a final property, we mention one which is proved in [10] and which will be
helpful in proving results in the following sections.

######  Theorem 10 ([10]).

Let $G,H$ and $F_{1},\cdots,F_{r}$ be $r+2$ graphs, and let
$\alpha_{1},\cdots,\alpha_{r}$ be $r$ positive numbers such that

  * •

$\displaystyle\mathcal{B}(G)=\mathcal{B}(H)+\sum_{i=1}^{r}\alpha_{i}\mathcal{B}(F_{i})$,

  * •

$\displaystyle\mathcal{T}(G)=\mathcal{T}(H)+\sum_{i=1}^{r}\alpha_{i}\mathcal{T}(F_{i})$,
and

  * •

$\displaystyle\mathcal{A}(F_{i})<\mathcal{A}(H)$ for all $i=1,\cdots,r$.

Then $\mathcal{A}(G)<\mathcal{A}(H)$.

##  4 Some values for $\mathcal{A}(G)$

The value $\mathcal{A}(G)$ is known for some graphs $G$. We mention here some
of them which are proven in [10] and determine some others.

######  Proposition 11.

[10]

  * •

$\displaystyle\mathcal{A}(\overline{{\sf K}}_{n})=\mathcal{A}(n{\sf
K}_{1})=\frac{{\sf B}_{n+1}-{\sf B}_{n}}{{\sf B}_{n}}$ for all $n\geq 1$;

  * •

$\displaystyle\mathcal{A}(T\cup p{\sf
K}_{1})=\frac{\displaystyle\sum_{i=0}^{p}{p\choose i}{\sf
B}_{n+i}}{\displaystyle\sum_{i=0}^{p}{p\choose i}{\sf B}_{n+i-1}}$ for all
trees $T$ of order $n\geq 1$ and all $p\geq 0$;

  * •

$\displaystyle\mathcal{A}({\sf C}_{n}\cup p{\sf
K}_{1})=\frac{\displaystyle\sum_{j=1}^{n-1}(-1)^{j+1}\sum_{i=0}^{p}{p\choose
i}{\sf
B}_{n+i-j+1}}{\displaystyle\sum_{j=1}^{n-1}(-1)^{j+1}\sum_{i=0}^{p}{p\choose
i}{\sf B}_{n+i-j}}$ for all $n\geq 3$ and $p\geq 0$.

Since $S({\sf K}_{n},k)=1$ for $k=n$, and $S({\sf K}_{n},k)=0$ for $k<n$, we
have $\mathcal{A}({\sf K}_{n})=n$. We prove here a stronger property which we
use in the next section. Let $\genfrac{\\{}{\\}}{0.0pt}{}{a}{b}$ be the
Stirling number of the second kind, with parameters $a$ and $b$ (i.e., the
number of partitions of a set of $a$ elements into $b$ blocks).

######  Proposition 12.

$\quad\displaystyle\mathcal{A}({\sf K}_{n}\cup p{\sf
K}_{1})=\frac{\displaystyle\sum_{k=n}^{n+p}k\sum_{j=0}^{n}{k-j\choose
n-j}{n\choose
j}(n-j)!\genfrac{\\{}{\\}}{0.0pt}{}{p}{k-j}}{\displaystyle\sum_{k=n}^{n+p}\sum_{j=0}^{n}{k-j\choose
n-j}{n\choose j}(n-j)!\genfrac{\\{}{\\}}{0.0pt}{}{p}{k-j}}\quad$ for all
$n\geq 1$ and all $p\geq 0$.

###### Proof.

It is proved in [11] that given two graphs $G_{1}$ and $G_{2}$, we have

$S(G_{1}\cup G_{2},k)=\sum_{i=1}^{k}\sum_{j=0}^{i}{i\choose j}{k-j\choose
i-j}(i-j)!S(G_{1},i)S(G_{2},k-j).$

For $G_{1}\simeq{\sf K}_{n}$ and $G_{2}\simeq p{\sf K}_{1}$, we have
$S(G_{1},i)=1$ if $i=n$, and $S(G_{1},i)=0$ otherwise. Also,
$S(G_{2},k-j)=\genfrac{\\{}{\\}}{0.0pt}{}{p}{k-j}$. Hence,

$S({\sf K}_{n}\cup p{\sf K}_{1},k)=\sum_{j=0}^{n}{k-j\choose n-j}{n\choose
j}(n-j)!\genfrac{\\{}{\\}}{0.0pt}{}{p}{k-j}.$

The result then follows from the fact that

$\displaystyle\mathcal{A}({\sf K}_{n}\cup p{\sf
K}_{1})=\frac{\displaystyle\sum_{k=n}^{n+p}kS({\sf K}_{n}\cup p{\sf
K}_{1},k)}{\displaystyle\sum_{k=n}^{n+p}S({\sf K}_{n}\cup p{\sf K}_{1},k)}.$

∎

We now determine $\mathcal{A}(G)$ for $G$ equal to the complement of a path
and the complement of a cycle. In what follows, we write $F_{n}$ and $L_{n}$
for the $n$th Fibonacci number and the $n$th Lucas number, respectively.

######  Proposition 13.

$\displaystyle\mathcal{A}({\sf\overline{P}}_{n})=\frac{(n+1)F_{n+2}+(2n-1)F_{n+1}}{5F_{n+1}}$
for all $n\geq 1$.

###### Proof.

The result is true for $n\leq 2$. Indeed,

  * •

For $n=1$, we have ${\sf\overline{P}}_{1}=K_{1}$ which implies
$\mathcal{A}({\sf\overline{P}}_{1})=1=\frac{2F_{3}+F_{2}}{5F_{2}}$;

  * •

For $n=2$, we have ${\sf\overline{P}}_{2}=\overline{K}_{2}$ which implies
$\mathcal{A}({\sf\overline{P}}_{2})=\frac{{\sf B}_{3}-{\sf B}_{2}}{{\sf
B}_{2}}=\frac{3}{2}=\frac{3F_{4}+3F_{3}}{5F_{3}}$.

For larger values of $n$, we proceed by induction. It is shown in [8] that
$\mathcal{B}({\sf\overline{P}}_{n}){=}F_{n+1}$. Also, it follows from
Equations (8) that
$\mathcal{T}({\sf\overline{P}}_{n})=\mathcal{T}({\sf\overline{P}}_{n-1}+{\sf
K}_{1})+\mathcal{T}({\sf\overline{P}}_{n-2}+{\sf K}_{1})$. Moreover, as shown
in the proof of Theorem 1, we have

$\mathcal{T}(G+{\sf K}_{1})=\mathcal{T}(G)\mathcal{B}({\sf
K}_{1})+\mathcal{B}(G)\mathcal{T}({\sf K}_{1})=\mathcal{T}(G)+\mathcal{B}(G).$

Hence,

$\displaystyle\mathcal{A}({\sf\overline{P}}_{n})$
$\displaystyle=\frac{\mathcal{T}({\sf\overline{P}}_{n-1})+\mathcal{B}({\sf\overline{P}}_{n-1})+\mathcal{T}({\sf\overline{P}}_{n-2})+\mathcal{B}({\sf\overline{P}}_{n-2})}{F_{n+1}}$
$\displaystyle=\frac{nF_{n+1}+(2n-3)F_{n}}{5F_{n+1}}+\frac{F_{n}}{F_{n+1}}+\frac{(n-1)F_{n}+(2n-5)F_{n-1}}{5F_{n+1}}+\frac{F_{n-1}}{F_{n+1}}$
$\displaystyle=\frac{nF_{n+1}+(3n+1)F_{n}+2nF_{n-1}}{5F_{n+1}}=\frac{3nF_{n+1}+(n+1)F_{n}}{5F_{n+1}}$
$\displaystyle=\frac{(n+1)F_{n+2}+(2n-1)F_{n+1}}{5F_{n+1}}.$

∎

######  Proposition 14.

$\displaystyle\mathcal{A}({\sf\overline{C}}_{n})=\frac{nF_{n+1}}{L_{n}}$ for
all $n\geq 4$.

###### Proof.

It follows from Equations (8) that

$\mathcal{T}({\sf\overline{C}}_{n})=\mathcal{T}({\sf\overline{P}}_{n})+\mathcal{T}({\sf\overline{P}}_{n-2}+{\sf
K}_{1}).$

Moreover, it is shown in [8] that $\mathcal{B}({\sf\overline{C}}_{n})=L_{n}$.
Since $\mathcal{T}({\sf\overline{P}}_{n-2}+{\sf
K}_{1})=\mathcal{T}({\sf\overline{P}}_{n-2})+\mathcal{B}({\sf\overline{P}}_{n-2})$,
Proposition 13 implies

$\displaystyle\mathcal{A}({\sf\overline{C}}_{n})$
$\displaystyle=\frac{\mathcal{T}({\sf\overline{P}}_{n})+\mathcal{T}({\sf\overline{P}}_{n-2})+\mathcal{B}({\sf\overline{P}}_{n-2})}{L_{n}}$
$\displaystyle=\frac{(n+1)F_{n+2}+(2n-1)F_{n+1}}{5L_{n}}+\frac{(n-1)F_{n}+(2n-5)F_{n-1}}{5L_{n}}+\frac{F_{n-1}}{L_{n}}$
$\displaystyle=\frac{(n+1)F_{n+2}+(2n-1)F_{n+1}+(n-1)F_{n}+2nF_{n-1}}{5L_{n}}$
$\displaystyle=\frac{3nF_{n+1}+2nF_{n}+2nF_{n-1}}{5L_{n}}=\frac{5nF_{n+1}}{5L_{n}}=\frac{nF_{n+1}}{L_{n}}.$

∎

##  5 Lower bounds on $\mathcal{A}(G)$

In this section, we give three conjectures for potential lower bounds on
$\mathcal{A}(G)$. We then establish their validity for triangulated graphs and
for graphs $G$ with maximum degree $\Delta(G)\leq 2$.

###  5.1 Conjectures

The lower bounds we are interested in depend on two parameters $n$ and $r$
with $1{\leq}r{\leq}n$. They are equal to $\mathcal{A}(G)$ for some specific
graphs $G$. More precisely, with the help of Propositions 11 and 12, we define

  * •

$L_{1}(n)=\mathcal{A}(\overline{{\sf K}}_{n})=\frac{\displaystyle{\sf
B}_{n+1}-{\sf B}_{n}}{\displaystyle{\sf B}_{n}}$,

  * •

$L_{2}(n,r)=\mathcal{A}({\sf K}_{r}\cup(n{-}r){\sf
K}_{1})=\frac{\displaystyle\sum_{k=r}^{n}k\sum_{i=0}^{r}{k-i\choose
r-i}{r\choose
i}(r-i)!\genfrac{\\{}{\\}}{0.0pt}{}{n-r}{k-i}}{\displaystyle\sum_{k=r}^{n}\sum_{i=0}^{r}{k-i\choose
r-i}{r\choose i}(r-i)!\genfrac{\\{}{\\}}{0.0pt}{}{n-r}{k-i}}$,

  * •

$L_{3}(n,r)=\mathcal{A}({\sf K}_{1,r{-}1}\cup(n{-}r){\sf
K}_{1})=\frac{\displaystyle\sum_{i=0}^{n{-}r}{n{-}r\choose i}{\sf
B}_{r+i}}{\displaystyle\sum_{i=0}^{n{-}r}{n{-}r\choose i}{\sf B}_{r+i{-}1}}$.

(a)  (b)  (c)

Figure 2: The three graphs that define the lower bounds $L_{1}(7)$,
$L_{2}(7,4)$ and $L_{3}(7,4)$.

For illustration, we show in Figure 2 the three graphs that give the bounds
for $n=7$ and $r=4$.

Given a graph $G$ of order $n$, we are interested in the following
inequalities, one of them being a conjecture, the other ones being proved here
below:

$L_{1}(n){\leq}{\min}\Big{\\{}L_{2}(n,\chi(G)),L_{3}(n,\Delta(G){+}1)\Big{\\}}{\leq}{\max}\Big{\\{}L_{2}(n,\chi(G)),L_{3}(n,\Delta(G){+}1)\Big{\\}}{\leq}\mathcal{A}(G).$

The first inequality follows from Theorem 7 since $\overline{{\sf K}}_{n}$ is
obtained from ${\sf K}_{r}{\cup}(n{-}r){\sf K}_{1}$ and from ${\sf
K}_{1,r{-}1}{\cup}(n{-}r){\sf K}_{1}$ by repeatedly removing edges incident to
simplicial vertices. The second inequality is trivial. The last inequality is
an open problem stated in the two following conjectures.

######  Conjecture 15.

Let $G$ be a graph of order $n$. Then,

$\mathcal{A}(G)\geq L_{2}(n,\chi(G))$

with equality if and only if $G\simeq{\sf K}_{\chi(G)}\cup(n{-}\chi(G)){\sf
K}_{1}$.

######  Conjecture 16.

Let $G$ be a graph of order $n$. Then

$\mathcal{A}(G)\geq L_{3}(n,\Delta(G){+}1)$

with equality if and only if $G\simeq{\sf
K}_{1,\Delta(G)}\cup(n{-}\Delta(G){-}1){\sf K}_{1}$.

Since $L_{1}(n)\leq\min\\{L_{2}(n,\chi(G)),L_{3}(n,\Delta(G){+}1)\\}$, it
suffices to show that one of these conjectures is true to prove that the empty
graph $\overline{{\sf K}}_{n}$ has the minimum value for $\mathcal{A}(G)$
among all graphs $G$ of order $n$. This leads to the following weaker
conjecture.

######  Conjecture 17.

Let $G$ be a graph of order $n$, then,

$\mathcal{A}(G)\geq L_{1}(n)$

with equality if and only if $G\simeq\overline{{\sf K}}_{n}$.

######  Theorem 18.

Conjectures 15 and 16 (and therefore 17) are true for triangulated graphs.

###### Proof.

Let us first observe that removing an edge incident to a simplicial vertex in
a triangulated graph gives another triangulated graph. So let $G$ be a
triangulated graph. Since $G$ is perfect, it contains a clique $K$ of order
$|K|=\chi(G)$. It is well known that triangulated graphs that are not a clique
contain at least two non-adjacent simplicial vertices [5]. Hence, $G$ can be
reduced to ${\sf K}_{\chi(G)}\cup(n{-}\chi(G)){\sf K}_{1}$ by repeatedly
removing edges incident to simplicial vertices. We know from Theorem 7 that
each of these edge removals strictly decreases $\mathcal{A}(G)$. We thus have
$\mathcal{A}(G)\geq\mathcal{A}({\sf K}_{\chi(G)}\cup(n{-}\chi(G)){\sf
K}_{1})$, with equality if and only if $G\simeq{\sf
K}_{\chi(G)}\cup(n{-}\chi(G)){\sf K}_{1}$. Conjecture 15 is therefore true for
triangulated graphs.

Let us now deal with Conjecture 16. Let $v$ be a vertex of degree $\Delta(G)$
in $G$. We consider the partition $(N_{1}(v),N_{2}(v))$ of the neighborhood
$N(v)$ of $v$, where $N_{1}(v)$ contains all vertices of $N(v)$ of degree 1 in
$G$ (i.e., $v$ is the only neighbor of every vertex of $N_{1}(v)$). Also, we
consider the partition $(\overline{N}_{1}(v),\overline{N}_{2}(v))$ of the set
$\overline{N}(v)$ of vertices of $G$ that are not adjacent to $v$, where
$\overline{N}_{1}(v)$ contains all vertices of $\overline{N}(v)$ of degree 0
in $G$. If $N_{2}(v)\cup\overline{N}_{2}(v)\neq\emptyset$ then
$G[N_{2}(v)\cup\overline{N}_{2}(v)\cup\\{v\\}]$ contains a simplicial vertex
$w\neq v$ (since it is also a triangulated graph which is not a clique).
Clearly, $w$ is simplicial in the whole graph that includes $N_{1}(v)$ and
$\overline{N}_{1}(v)$. Then :

  * •

If $w\in N_{2}(G)$, we can remove all edges incident to $w$, except the one
that links $w$ with $v$. We thus get a new triangulated graph in which at
least one vertex has been transferred from $N_{2}(v)$ to $N_{1}(v)$, vertices
of $\overline{N}_{2}(v)$ may have transferred to $\overline{N}_{1}(v)$, but no
vertex has undergone the reverse transfers.

  * •

If $w\in\overline{N}_{2}(v)$, we can remove all edges incident to $w$. We thus
get a new triangulated graph in which at least one vertex has been transferred
from $\overline{N}_{2}(v)$ to $\overline{N}_{1}(v)$, vertices of $N_{2}(v)$
may have transferred to $N_{1}(v)$, but no vertex has undergone the reverse
transfers.

Note that in both cases, no vertex has been transferred from $\overline{N}(v)$
to $N(v)$ or vice versa. Hence, by repeatedly applying the above mentioned
edge removals, we get $N_{2}(v)=\overline{N}_{2}(v)=\emptyset$, which means
that the resulting graph is ${\sf K}_{1,\Delta(G)}\cup(n{-}\Delta(G)-1){\sf
K}_{1}$. Again, we know from Theorem 7 that each of the edge removals
performed strictly decreases $\mathcal{A}(G)$, which proves that
$\mathcal{A}(G)\geq\mathcal{A}({\sf K}_{1,\Delta(G)}\cup(n{-}\Delta(G)-1){\sf
K}_{1})$, with equality if and only if $G\simeq{\sf
K}_{1,\Delta(G)}\cup(n{-}\Delta(G)-1){\sf K}_{1}$. ∎

The three conjectures come from the discovery systems _GraPHedron_ [13] and
_PHOEG_ [3]. Note that despite the apparent simplicity of Conjecture 17, its
validity cannot be proven by simple intuitive means such as sequential edge
removal. Indeed, there are graphs, for example ${\sf K}_{2,4}$, for which the
removal of any edge strictly increases $\mathcal{A}(G)$. Also, we cannot
proceed by induction on the the number of connected components of $G$. Indeed,
there are pairs of graphs $G_{1},G_{2}$ such that
$\mathcal{A}(G_{1})<\mathcal{A}(G_{2})$ while $\mathcal{A}(G_{1}{\cup}{\sf
K}_{1})>\mathcal{A}(G_{2}{\cup}{\sf K}_{1})$. For example, for $G_{1}={\sf
K}_{2,3}$ and $G_{2}={\sf K}_{3}{\cup}2{\sf K}_{1}$, we have

$\mathcal{A}(G_{1})=3.5<3.529=\mathcal{A}(G_{2})\quad\quad\mbox{and}\quad\quad\mathcal{A}(G_{1}{\cup}{\sf
K}_{1})=3.867>3.831=\mathcal{A}(G_{2}{\cup}{\sf K}_{1}).$

Note that proving that Conjecture 16 is true for all graphs $G$ of order $n$
and maximum degree $\Delta(G)=n-1$ is as difficult as proving Conjecture 17.
Indeed, let $v$ be a vertex of degree $n-1$ in a graph $G$ of order $n$. Since
$v$ is a dominant vertex of $G$, we know from Corollary 2 that
$\mathcal{A}(G)=\mathcal{A}(G-v)$+1. Hence, minimizing $\mathcal{A}(G)$ is
equivalent to minimizing $\mathcal{A}(G-v)$, with no maximum degree constraint
on $G-v$. We show in the next section that Conjectures 15 and 16 (and
therefore 17) are true for graphs of maximum degree at most 2.

###  5.2 Proof of the conjectures for graphs $G$ with $\Delta(G)\leq 2$

We start this section with a simple proof of the validity of Conjectures 15
and 16 when $\Delta(G)=1$.

######  Theorem 19.

Let $G$ be a graph of order $n$ and maximum degree $\Delta(G)=1$. Then,

$L_{2}(n,\chi(G))=L_{3}(n,\Delta(G){+}1)\leq\mathcal{A}(G),$

with equality if and only if $G\simeq{\sf K}_{2}{\cup}(n{-}2){\sf K}_{1}$.

###### Proof.

Since $\Delta(G)=1$, we have $\chi(G)=2$, which implies

$L_{2}(n,\chi(G)){=}L_{2}(n,2){=}\mathcal{A}({\sf K}_{2}{\cup}(n{-}2){\sf
K}_{1}){=}\mathcal{A}({\sf K}_{1,1}{\cup}(n{-}2){\sf
K}_{1})=L_{3}(n,2){=}L_{3}(n,\Delta(G){+}1).$

Note also that $\Delta(G)=1$ implies $G\simeq p{\sf K}_{2}{\cup}(n{-}2p){\sf
K}_{1}$ for $p\geq 1$. Hence, all vertices in $G$ are simplicial. We can thus
sequentially remove all edges of $G$, except one, and it follows from Theorem
7 that $\mathcal{A}(G)\geq\mathcal{A}({\sf K}_{2}{\cup}(n{-}2){\sf K}_{1})$,
with equality if and only $G\simeq{\sf K}_{2}{\cup}(n{-}2){\sf K}_{1}$. ∎

The proofs that Conjectures 15 and 16 are true when $\Delta(G)=2$ are more
complex. We first prove some intermediate results in the form of lemmas.

######  Lemma 20.

$\mathcal{A}(G\cup{\sf C}_{n})>\mathcal{A}(G\cup{\sf P}_{n})$ for all $n\geq
3$ and all graphs $G$.

###### Proof.

Let $H\simeq{\sf P}_{2}$ if $n=3$ and $H\simeq{\sf C}_{n-1}$ if $n>3$. We know
from Equations (5) that $\mathcal{B}(G\cup{\sf C}_{n})=\mathcal{B}(G\cup{\sf
P}_{n})-\mathcal{B}(G\cup H)$ and $\mathcal{T}(G\cup{\sf
C}_{n})=\mathcal{T}(G\cup{\sf P}_{n})-\mathcal{T}(G\cup H)$. Since ${\sf
P}_{n}$ is a partial subgraph of ${\sf C}_{n}$, we have $\mathcal{B}(G\cup{\sf
C}_{n})>\mathcal{B}(G\cup{\sf P}_{n})$. Altogether, this gives

$\displaystyle\mathcal{A}(G\cup{\sf C}_{n})-\mathcal{A}(G\cup H)$
$\displaystyle=\frac{\mathcal{T}(G\cup{\sf C}_{n})}{\mathcal{B}(G\cup{\sf
C}_{n})}-\frac{\mathcal{T}(G\cup H)}{\mathcal{B}(G\cup H)}$
$\displaystyle=\frac{\mathcal{T}(G\cup{\sf P}_{n})-\mathcal{T}(G\cup
H)}{\mathcal{B}(G\cup{\sf P}_{n})-\mathcal{B}(G\cup
H)}-\frac{\mathcal{T}(G\cup H)}{\mathcal{B}(G\cup H)}$
$\displaystyle=\frac{\mathcal{T}(G\cup{\sf P}_{n})\mathcal{B}(G\cup
H)-\mathcal{T}(G\cup H)\mathcal{B}(G\cup{\sf P}_{n})}{\mathcal{B}(G\cup{\sf
C}_{n})\mathcal{B}(G\cup H)}$ $\displaystyle>\frac{\mathcal{T}(G\cup{\sf
P}_{n})\mathcal{B}(G\cup H)-\mathcal{T}(G\cup H)\mathcal{B}(G\cup{\sf
P}_{n})}{\mathcal{B}(G\cup{\sf P}_{n})\mathcal{B}(G\cup H)}$
$\displaystyle=\frac{\mathcal{T}(G\cup{\sf P}_{n})}{\mathcal{B}(G\cup{\sf
P}_{n})}-\frac{\mathcal{T}(G\cup H)}{\mathcal{B}(G\cup H)}$
$\displaystyle=\mathcal{A}(G\cup{\sf P}_{n})-\mathcal{A}(G\cup H)$
$\displaystyle\iff$ $\displaystyle\mathcal{A}(G\cup{\sf
C}_{n})>\mathcal{A}(G\cup{\sf P}_{n}).$

For $n\geq 3$, let ${\sf Q}_{n}$ be the graph obtained from ${\sf P}_{n}$ by
adding an edge between an extremity $v$ of ${\sf P}_{n}$ and the vertex at
distance 2 from $v$ on ${\sf P}_{n}$.

######  Lemma 21.

If $n\geq 3$, $0\leq x\leq p$ and $1\leq k\leq n$, then

$S({\sf Q}_{n}\cup p{\sf K}_{1},k)=\sum_{i=0}^{x}{x\choose i}S({\sf
Q}_{n+i}\cup(p-x){\sf K}_{1},k).$

###### Proof.

The result is clearly true for $p=0$. For larger values of $p$, we proceed by
induction. Since the result is clearly true for $x=0$, we assume $x\geq 1$.
Equations (2) imply

$\displaystyle S({\sf Q}_{n}\cup p{\sf K}_{1},k)$ $\displaystyle=S({\sf
Q}_{n+1}\cup(p{-}1){\sf K}_{1},k)+S({\sf Q}_{n}\cup(p{-}1){\sf K}_{1},k)$
$\displaystyle=$ $\displaystyle\sum_{i=0}^{x-1}{x{-}1\choose i}S({\sf
Q}_{n+i+1}\cup(p{-}x){\sf K}_{1},k)+\sum_{i=0}^{x-1}{x{-}1\choose i}S({\sf
Q}_{n+i}\cup(p{-}x){\sf K}_{1},k)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{x}{x{-}1\choose i{-}1}S({\sf Q}_{n+i}\cup(p{-}x){\sf
K}_{1},k)+\sum_{i=0}^{x-1}{x{-}1\choose i}S({\sf Q}_{n+i}\cup(p{-}x){\sf
K}_{1},k)$ $\displaystyle=$ $\displaystyle S({\sf Q}_{n{+}x}{\cup}(p{-}x){\sf
K}_{1},k){+}S({\sf Q}_{n}{\cup}(p{-}x){\sf K}_{1},k)$
$\displaystyle+\sum_{i=1}^{x-1}\left({x{-}1\choose i{-}1}+{x{-}1\choose
i}\right)S({\sf Q}_{n{+}i}{\cup}(p{-}x){\sf K}_{1},k)$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{x}{x\choose i}S({\sf Q}_{n+i}\cup(p{-}x){\sf
K}_{1},k).\vspace{-1cm}\qed$

######  Lemma 22.

If $n\geq 3$ is an odd number and $1\leq k\leq n$, then

$S({\sf C}_{n}\cup p{\sf K}_{1},k)=\sum_{i=0}^{(n-3)/2}S({\sf Q}_{2i+3}\cup
p{\sf K}_{1},k).$

###### Proof.

The result is clearly true for $n=3$ since ${\sf C}_{3}\simeq{\sf Q}_{3}$. For
larger values of $n$, we proceed by induction. It follows from Equations (1)
and (2) that

$\displaystyle S({\sf C}_{n}\cup p{\sf K}_{1},k)$ $\displaystyle=S({\sf
P}_{n}\cup p{\sf K}_{1})-S({\sf C}_{n-1}\cup p{\sf K}_{1},k)$
$\displaystyle=\Bigl{(}S({\sf Q}_{n}{\cup}p{\sf K}_{1},k){+}S({\sf
P}_{n{-}1}{\cup}p{\sf K}_{1},k)\Bigr{)}{-}\Bigl{(}S({\sf P}_{n{-}1}{\cup}p{\sf
K}_{1},k){-}S({\sf C}_{n{-}2}{\cup}p{\sf K}_{1},k)\Bigr{)}$
$\displaystyle=S({\sf Q}_{n}\cup p{\sf K}_{1},k)+S({\sf C}_{n-2}\cup p{\sf
K}_{1},k)$ $\displaystyle=S({\sf Q}_{n}\cup p{\sf
K}_{1},k)+\sum_{i=0}^{(n-5)/2}S({\sf Q}_{2i+3}\cup p{\sf K}_{1},k)$
$\displaystyle=\sum_{i=0}^{(n-3)/2}S({\sf Q}_{2i+3}\cup p{\sf K}_{1},k).$

∎

######  Lemma 23.

If $n$ and $x$ are two numbers such that $5\leq x\leq n$ and $x$ is odd, then

$\smash{S}({\sf C}_{3}\cup(n-3){\sf K}_{1},k)=S({\sf C}_{x}\cup(n-x){\sf
K}_{1},k)+\sum_{i=0}^{x-5}\alpha_{i}S({\sf Q}_{i+4}\cup(n-x){\sf K}_{1},k)$

where

$\alpha_{i}=\begin{cases}\displaystyle{x-3\choose i}-1&\mbox{if }i\mbox{ is
even}\\\\[14.22636pt] \displaystyle{x-3\choose i}&\mbox{if }i\mbox{ is
odd.}\end{cases}$

###### Proof.

Since ${\sf Q}_{3}\simeq{\sf C}_{3}$ we know from Lemma 21 that

$\displaystyle S({\sf Q}_{3}\cup(n-3){\sf K}_{1},k)=$
$\displaystyle\sum_{i=0}^{x-3}{x-3\choose i}S({\sf Q}_{i+3}{\cup}(n-x){\sf
K}_{1},k)$ $\displaystyle=$ $\displaystyle\sum_{i=0}^{(x{-}3)/2}{x{-}3\choose
2i}S({\sf Q}_{2i+3}{\cup}(n{-}x){\sf K}_{1},k)$
$\displaystyle{+}\sum_{i=0}^{(x{-}5)/2}{x{-}3\choose 2i+1}S({\sf
Q}_{2i+4}\cup(n{-}x){\sf K}_{1},k).$

It then follows from Lemma 22 that

$\displaystyle S({\sf Q}_{3}{\cup}(n{-}3){\sf K}_{1},k){=}$ $\displaystyle
S({\sf C}_{x}{\cup}(n{-}x){\sf
K}_{1},k){+}\sum_{i=1}^{(x{-}5)/2}\left({x{-}3\choose 2i}{-}1\right)S({\sf
Q}_{2i+3}{\cup}(n{-}x){\sf K}_{1},k)$
$\displaystyle+\sum_{i=0}^{(x-5)/2}{x-3\choose 2i+1}S({\sf
Q}_{2i+4}\cup(n-x){\sf K}_{1},k)$ $\displaystyle=$ $\displaystyle S({\sf
C}_{x}\cup(n-x){\sf K}_{1},k)+\sum_{i=0}^{x-5}\alpha_{i}S({\sf
Q}_{i+4}\cup(n-x){\sf K}_{1},k).$

∎

######  Lemma 24.

If $n\geq 5$ and $3\leq i<n$ then

$\mathcal{A}({\sf Q}_{i}\cup p{\sf K}_{1})<\mathcal{A}({\sf C}_{n}\cup p{\sf
K}_{1})$

###### Proof.

Since ${\sf Q}_{n-1}\cup p{\sf K}_{1}$ is obtained from ${\sf Q}_{i}\cup p{\sf
K}_{1}$ by iteratively adding vertices of degree $1$, we know from Corollary 5
that $\mathcal{A}({\sf Q}_{i}\cup p{\sf K}_{1})\leq\mathcal{A}({\sf
Q}_{n-1}\cup p{\sf K}_{1})$. Moreover, it is proved in [10] that
$\mathcal{A}({\sf Q}_{n-1}\cup p{\sf K}_{1})<\mathcal{A}({\sf P}_{n}\cup p{\sf
K}_{1})$ for all $n\geq 5$ and $p\geq 0$. It then follows from Lemma 20 that

$\mathcal{A}({\sf Q}_{i}\cup p{\sf K}_{1})\leq\mathcal{A}({\sf Q}_{n-1}\cup
p{\sf K}_{1})<\mathcal{A}({\sf P}_{n}\cup p{\sf K}_{1})<\mathcal{A}({\sf
C}_{n}\cup p{\sf K}_{1}).$

∎

######  Corollary 25.

If $n\geq 5$, $x$ is odd and $5\leq x\leq n$, then

$\mathcal{A}({\sf C}_{3}\cup(n-3){\sf K}_{1})<\mathcal{A}({\sf
C}_{x}\cup(n-x){\sf K}_{1}).$

###### Proof.

Lemma 23 implies

  * •

$\mathcal{B}({\sf C}_{3}\cup(n-3){\sf K}_{1})=\mathcal{B}({\sf
C}_{x}\cup(n-x){\sf
K}_{1})+\displaystyle\sum_{i=0}^{x-5}\alpha_{i}\mathcal{B}({\sf
Q}_{i+4}\cup(n-x){\sf K}_{1})$, and

  * •

$\mathcal{T}({\sf C}_{3}\cup(n-3){\sf K}_{1})=\mathcal{T}({\sf
C}_{x}\cup(n-x){\sf
K}_{1})+\displaystyle\sum_{i=0}^{x-5}\alpha_{i}\mathcal{T}({\sf
Q}_{i+4}\cup(n-x){\sf K}_{1})$,

where

  * •

$\alpha_{i}=\displaystyle{x-3\choose i}-1\geq 0$ if $i$ is even, and

  * •

$\alpha_{i}=\displaystyle{x-3\choose i}>0$ if $i$ is odd.

Also, we know from Lemma 24 that $\mathcal{A}({\sf Q}_{i+4}\cup p{\sf
K}_{1}){<}\mathcal{A}({\sf C}_{x}\cup(n-x){\sf K}_{1})$ for
$i=0,\ldots,x{-}5$. Hence, it follows from Theorem 10 that $\mathcal{A}({\sf
C}_{3}\cup(n-3){\sf K}_{1})<\mathcal{A}({\sf C}_{x}\cup(n-x){\sf K}_{1})$.

∎

We are now ready to prove the validity of Conjectures 15 and 16 when
$\Delta(G)=2$.

######  Theorem 26.

Let $G$ be a graph of order $n$ with $\Delta(G)=2$. Then,

$\mathcal{A}(G)\geq L_{2}(n,\chi(G))$

with equality if and only if $G\simeq{\sf K}_{\chi(G)}\cup(n{-}\chi(G)){\sf
K}_{1}$.

###### Proof.

Since $\Delta(G)=2$, $G$ is the disjoint union of paths and cycles. If $G$
does not contain any odd cycle, then $\chi(G)=2$. It then follows from Theorem
7 and Lemma 20 that the edges of $G$ can be removed sequentially, with a
strict decrease of $\mathcal{A}(G)$ at each step, until we get ${\sf
K}_{2}\cup(n{-}2){\sf K}_{1}$.

If $\chi(G){=}3$, then at least one connected component of $G$ is an odd cycle
${\sf C}_{x}$ with $x{\leq}n$. Again, we know from Theorem 7 and Lemma 20 that
the edges of $G$ can be removed sequentially, with a strict decrease of
$\mathcal{A}(G)$ at each step, until we get ${\sf C}_{x}\cup(n{-}x){\sf
K}_{1}$. It then follows from Corollary 25 that
$\mathcal{A}(G)\geq\mathcal{A}({\sf C}_{x}\cup(n{-}x){\sf
K}_{1})\geq\mathcal{A}({\sf C}_{3}\cup(n{-}3){\sf K}_{1})$, with equalities if
and only if $G\simeq{\sf C}_{3}\cup(n{-}3){\sf K}_{1}\simeq{\sf
K}_{3}\cup(n{-}3){\sf K}_{1}$.

∎

######  Theorem 27.

Let $G$ be a graph of order $n$ with $\Delta(G)=2$. Then,

$\mathcal{A}(G)\geq L_{3}(n,\Delta(G)+1)$

with equality if and only if $G\simeq{\sf K}_{1,2}\cup(n{-}3){\sf K}_{1}$.

###### Proof.

Since $\Delta(G)=2$, $G$ is the disjoint union of paths and cycles. Also, $G$
contains at least one vertex $u$ of degree 2. Let $v$ and $w$ be two neighbors
of $u$ in $G$. It follows from Theorem 7 and Lemma 20 that the edges of $G$
can be removed sequentially, with a strict decrease of $\mathcal{A}(G)$ at
each step, until the edge set of the remaining graph $H$ is $\\{uv,uw\\}$. But
$H$ is then isomorphic to ${\sf K}_{1,2}\cup(n{-}3){\sf K}_{1}$. ∎

##  6 Concluding remarks

We have established several properties for a recently defined graph invariant,
namely the average number $\mathcal{A}(G)$ of colors in the non-equivalent
colorings of a graph $G$. We then looked at bounds for $\mathcal{A}(G)$. It is
easy to prove that $\mathcal{A}(G)\leq\mathcal{A}({\sf K}_{n})=n$ for all
graphs of order $n$, with equality if and only if $G\simeq{\sf K}_{n}$. Hence,
$n$ is the best possible upper bound on $\mathcal{A}(G)$ for a graph $G$ of
order $n$. We think that the best possible lower bound on $\mathcal{A}(G)$ for
a graph $G$ of order $n$ is $\mathcal{A}(\overline{{\sf K}}_{n})$. We have
shown that despite its apparent simplicity, this conjecture cannot be proven
using simple techniques like sequential edge removal. We have then refined
this conjecture by proposing lower bounds related to the chromatic number
$\chi(G)$ and to the maximum degree $\Delta(G)$ of $G$. We have thus stated
three open problems. We have shown that these three conjectures are true for
triangulated graphs and for graphs with maximum degree at most 2.

## References

  * [1] Absil, R., Camby, E., Hertz, A., and Mélot, H. A sharp lower bound on the number of non-equivalent colorings of graphs of order $n$ and maximum degree $n-3$.  Discrete Appl. Math. 234 (2018), 3–11.  Special Issue on the Ninth International Colloquium on Graphs and Optimization (GO IX), 2014.
  * [2] Alzer, H. On Engel’s inequality for Bell numbers.  J. of Integer Seq. 22 (2019).  Article 19.7.1.
  * [3] Devillez, G., Hauweele, P., and Mélot, H. PHOEG Helps to Obtain Extremal Graphs.  In Operations Research Proceedings 2018 (GOR (Gesellschaft fuer Operations Research e.V.)) (sept. 12-14 2019), B. Fortz and M. Labbé, Eds., Springer, Cham, p. 251 (Paper 32).
  * [4] Diestel, R. Graph Theory, second edition ed.  Springer-Verlag, 2017.
  * [5] Dirac, G. On rigid circuit graphs.  Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25 (1961), 71–76.
  * [6] Dong, F. M., Koh, K. M., and Teo, K. L. Chromatic polynomials and chromaticity of graphs.  World Scientific Publishing Company, 2005.
  * [7] Duncan, B. Bell and Stirling numbers for disjoint unions of graphs.  Congressus Numerantium 206 (01 2010).
  * [8] Duncan, B., and Peele, R. B. Bell and Stirling numbers for graphs.  J. Integer Seq. 12 (2009).  Article 09.7.1.
  * [9] Galvin, D.and Thanh, D.T. Stirling numbers of forests and cycles.  Electron. J. Comb. 20 (2013).  Paper P73.
  * [10] Hertz, A., Hertz, A., and Mélot, H. Using graph theory to derive inequalities for the Bell numbers.  Submitted. arXiv:2104.00552, 2021.
  * [11] Hertz, A., and Mélot, H. Counting the number of non-equivalent vertex colorings of a graph.  Discrete Appl. Math. 203 (2016), 62–71.
  * [12] Kereskényi-Balogh, Z., and Nyul, G. Stirling numbers of the second kind and Bell numbers for graphs.  Australas. J. Comb. 58 (2014), 264–274.
  * [13] Mélot, H. Facet defining inequalities among graph invariants: the system GraPHedron.  Discrete Appl. Math. 156 (2008), 1875 – 1891.
  * [14] Odlyzko, A., and Richmond, L. On the number of distinct block sizes in partitions of a set.  J. Comb. Theory Ser. A. 38, 2 (1985), 170–181.