# Characterization of $\alpha$-excellent $2$-trees

1Magda Dettlaff, 2Michael A. Henning and 3Jerzy Topp

1Faculty of Mathematics, Physics and Informatics
University of Gdańsk
80-952 Gdańsk, Poland
<EMAIL_ADDRESS>

2Department of Mathematics and Applied Mathematics
University of Johannesburg
Auckland Park 2006, South Africa
<EMAIL_ADDRESS>

3Institute of Applied Informatics
University of Applied Sciences
82-300 Elbla̧g, Poland
<EMAIL_ADDRESS>Research supported in part by the University of
Johannesburg

###### Abstract

A graph is $\alpha$-excellent if every vertex of the graph is contained in
some maximum independent set of the graph. In this paper, we present two
characterizations of the $\alpha$-excellent $2$-trees.

Keywords: independence number; excellent graph; $k$-tree.
AMS subject classification: 05C69, 05C85

##  1 Introduction

For notation and graph theory terminology we, in general, follow the recent
books [9, 10, 11]. Specifically, let $G=(V(G),E(G))$ be a graph with vertex
set $V(G)$ and edge set $E(G)$. For a vertex $v$ of $G$, its _neighborhood_ ,
denoted by $N_{G}(v)$, is the set of all vertices adjacent to $v$. The _closed
neighborhood_ of $v$, denoted by $N_{G}[v]$, is the set $N_{G}(v)\cup\\{v\\}$.
For a set $S\subseteq V(G)$, the _open neighborhood_ of $S$ is the set
$N_{G}(S)=\bigcup_{v\in S}N_{G}(v)$, and the _closed neighborhood_
$N_{G}[S]=N_{G}(S)\cup S$. For a positive integer $k$, we let
$[k]=\\{1,\ldots,k\\}$.

A subset $D$ of the vertex set $V(G)$ of a graph $G$ is called a _dominating
set_ of $G$ if every vertex belonging to $V(G)\setminus D$ is adjacent to at
least one vertex in $D$. A subset $I$ of $V(G)$ is _independent_ if no two
vertices belonging to $I$ are adjacent in $G$. The cardinality of a largest
(i.e., maximum) independent set of $G$, denoted by $\alpha(G)$, is called the
_independence number_ of $G$. Every largest independent set of a graph is
called an $\alpha$-set of the graph. The _independent domination number_ of
$G$, denoted by $i(G)$, is the cardinality of the smallest independent
dominating set of $G$ (or equivalently, the cardinality of a minimum maximal
independent set of vertices in $G$). The _common independence number_ of a
graph $G$, denoted by $\alpha_{c}(G)$, is the greatest integer $r$ such that
every vertex of $G$ belongs to some independent subset $X$ of $V(G)$ with
$|X|\geq r$. It follows immediately from the above definitions that the common
independence number is bounded below by the independent domination number and
above by the independence number. Formally, for any graph $G$,

$i(G)\leq\alpha_{c}(G)\leq\alpha(G).$ (0)

The study of independent sets in graphs was begun by Berge [1, 2] (see also
[3]) and Ore [12]. We refer the reader to the book [11] and to the survey [8]
of results on independent domination in graphs published in 2013 by Goddard
and Henning. A graph $G$ is said to be _well-covered_ if $i(G)=\alpha(G)$.
Equivalently, $G$ is well-covered if every maximal independent set of $G$ is a
maximum independent set of $G$. The concept of well-covered graphs was
introduced by Plummer [13] in 1970. Since then the well-covered graphs were
very extensively investigating in many papers. We refer the reader to the
excellent (but already older) survey on well-covered graphs by Plummer [14].
We are interested in characterization of _$\alpha$ -excellent graphs_, that
is, graphs $G$ for which $\alpha_{c}(G)=\alpha(G)$. Thus, if $G$ is an
$\alpha$-excellent graph, every vertex belongs to some $\alpha$-set of $G$. It
follows from Inequalities ( ‣ 1) that every well-covered graph is an
$\alpha$-excellent graph. The example of the cycle $C_{6}$ shows that the set
of well-covered graphs is properly contained in the set of $\alpha$-excellent
graphs. The $\alpha$-excellent graphs have been studied in [4, 5, 6, 7, 15,
16] and in [1, 2] as $B$-graphs. In this paper, we begin the study of
$\alpha$-excellent $k$-trees.

##  2 Preliminary results

A vertex $v$ of a graph $G$ is a _simplicial vertex_ if every two vertices
belonging to $N_{G}(v)$ are adjacent in $G$. Equivalently, a simplicial vertex
is a vertex that appears in exactly one clique of a graph, where a  _clique_
of a graph $G$ is a maximal complete subgraph of $G$. A clique of a graph $G$
containing at least one simplicial vertex of $G$ is called a _simplex_ of $G$.
Note that if $v$ is a simplicial vertex of $G$, then $G[N_{G}[v]]$ is the
unique simplex of $G$ containing $v$. We begin with a simple proposition.

######  Proposition 2.1.

No $\alpha$-excellent graph contains a vertex belonging to at least two its
simplexes.

###### Proof.

Assume that a vertex $v$ of a graph $G$ belongs to two simplicies of $G$, say
to $G[N_{G}[u]]$ and $G[N_{G}[w]]$. If $I$ is a maximum independent set that
contains $v$, then $(I\setminus\\{v\\})\cup\\{u,w\\}$ is an independent set of
greater cardinality. Thus,
$\alpha(G)\geq|(I\setminus\\{v\\})\cup\\{u,w\\}|>|I|$, implying that $v$ does
not belong to any $\alpha$-set of $G$, and proving that $G$ is not an
$\alpha$-excellent graph. ∎

For a positive integer $k$, a graph $G$ is called a $k$-_tree_ if it can be
obtained from the complete graph $K_{k}$ by a finite number of applications of
the following operation: add a new vertex and join it to $k$ mutually adjacent
vertices of the existing graph. Certainly, every $1$-tree is a tree and vice
versa. In [17], Rose proved that a graph $G$ is a $k$-tree if and only if the
following conditions are fulfilled: $(i)$ $G$ is connected, $(ii)$ $G$
contains $K_{k}$ as a subgraph and does not contain $K_{k+2}$ as a subgraph,
$(iii)$ if $v$ and $u$ are nonadjacent vertices of $G$, then the subgraph
induced by the smallest $v\\!-\\!u$ separator is a complete graph on $k$
vertices. Note that $K_{k}$ and $K_{k+1}$ are the only $k$-trees of order $k$
and $k+1$, respectively.

It was proved in [4] that a bipartite graph (and, in particular, a tree) is an
$\alpha$-excellent graph if and only if it has a perfect matching. In this
paper we are interested in possible extensions of that characterization to a
characterization of $\alpha$-excellent $k$-trees for every positive integer
$k$. We begin with the following definition.

A set ${\cal P}$ of complete subgraphs of a graph $G$ is said to be a _perfect
$(k+1)$-cover_ of $G$ if each subgraph belonging to $\cal P$ is of order $k+1$
and every vertex of $G$ belongs to exactly one subgraph in ${\cal P}$. It is
obvious that for $k=1$ there exists a one-to-one correspondence between
perfect 2-covers of a graph and perfect matchings of the graph. Here we are
interested in the existence of perfect $(k+1)$-covers in $k$-trees. First of
all, one can prove that every $k$-tree has at most one perfect $(k+1)$-cover.
In the following proposition we present the first relationship between
$k$-trees having perfect $(k+1)$-covers and $\alpha$-excellent graphs.

######  Proposition 2.2.

If a $k$-tree $G$ has a perfect $(k+1)$-cover, then $G$ is an
$\alpha$-excellent graph.

###### Proof.

Let $G$ be a connected $k$-tree of order $n\geq k+1$. Then $G$ is a
$(k+1)$-partite graph, say $A_{1},A_{2},\ldots,A_{k+1}$ are partite sets of
$G$ and assume that $|A_{1}|\geq|A_{2}|\geq\ldots\geq|A_{k+1}|\geq 1$. In
addition, since $A_{1},A_{2},\ldots,A_{k+1}$ are independent sets of vertices
and $|A_{1}|+|A_{2}|+\cdots+|A_{k+1}|=n$, it follows that $|A_{1}|\geq
n/(k+1)$, and, therefore, $\alpha(G)\geq|A_{1}|\geq n/(k+1)$. Let $I$ be an
$\alpha$-set of $G$. Assume now that ${\cal P}=\\{P_{1},\ldots,P_{\ell}\\}$ is
a perfect $(k+1)$-cover of $G$. Then, ${\ell}=n/(k+1)$, $|I\cap
V({P_{i}})|\leq 1$ for each $i\in[\ell]$, and

$\alpha(G)=|I|=|I\cap\bigcup_{i=1}^{\ell}V({P_{i}})|=\sum_{i=1}^{\ell}|I\cap
V({P_{i}})|\leq\ell=\frac{n}{k+1}.$

Consequently, $|A_{1}|=|A_{2}|=\cdots=|A_{k+1}|=n/(k+1)=\alpha(G)$, and each
of the sets $A_{1},A_{2},\ldots,A_{k+1}$ is an $\alpha$-set of $G$. This
implies that every vertex of $G$ belongs to an $\alpha$-set of $G$ and,
therefore, $G$ is an $\alpha$-excellent graph. ∎

##  3 $\alpha$-Excellent $2$-trees

From Proposition 2.2 we know that a $k$-tree having a perfect $(k+1)$-cover is
an $\alpha$-excellent $k$-tree. It is not clear to us whether the converse of
this statement is true. That is, we do not know if every $\alpha$-excellent
$k$-tree of order at least $k+1$ has a perfect $(k+1)$-cover if $k\geq 3$.
However when $k=2$, we provide in this paper a characterization of
$\alpha$-excellent $k$-trees. For notational simplicity, in what follows if
three vertices $a$, $b$, and $c$ are mutually adjacent in a graph $G$, then
the induced subgraph $G[\\{a,b,c\\}]$ of $G$ is isomorphic to $K_{3}$ and is
called a _triangle_ in $G$, and we simply write $abc$ rather than
$G[\\{a,b,c\\}]$. To every triangle in a graph $G$, we assign label $R$ or $B$
(as red or blue, resp.), and by $R(G)$ and $B(G)$ we denote the set of all
triangles in $G$ that have label $R$ and $B$, respectively. We also say that
$R(G)$ and $B(G)$ are the sets of all ’’red‘‘ and ’’blue‘‘ triangles in $G$,
respectively.

We are now in position to present a constructive characterization of
$\alpha$-excellent $2$-trees. For this purpose, let $\cal E$ be the family of
labeled $2$-trees defined recursively as follows:

  1. (1)

The family $\cal E$ contains the $2$-tree of order $3$ in which the only
triangle is red, that is, it has label $R$.

  2. (2)

The family $\cal E$ is closed under the operations ${\cal O}_{1}$ and ${\cal
O}_{2}$ defined below:

     * •

Operation ${\cal O}_{1}$. If a graph $G^{\prime}$ belongs to ${\cal E}$ and
$v_{1}v_{2}$ is an edge of $G^{\prime}$, then ${\cal O}_{1}={\cal
O}_{1}(v_{1},v_{2})$ forms a graph $G$ by adding three new vertices $u_{1}$,
$u_{2}$, $u_{3}$ to $G^{\prime}$ in such a way that $v_{1}v_{2}u_{1}$,
$v_{2}u_{1}u_{2}$ and $u_{1}u_{2}u_{3}$ are three new triangles, while
$R(G)=R(G^{\prime})\cup\\{u_{1}u_{2}u_{3}\\}$ and
$B(G)=B(G^{\prime})\cup\\{v_{1}v_{2}u_{1},v_{2}u_{1}u_{2}\\}$. In this case we
say that we apply the operation ${\cal O}_{1}$ to the edge $v_{1}v_{2}$ of
$G^{\prime}$.

     * •

Operation ${\cal O}_{2}$. If a graph $G^{\prime}$ belongs to ${\cal E}$,
$v_{1}v_{2}v_{3}$ is a red triangle in $G^{\prime}$ (that is,
$v_{1}v_{2}v_{3}\in R(G^{\prime})$), and $v_{4}$ is a neighbor of $v_{3}$ (it
is possible that $v_{4}\in\\{v_{1},v_{2}\\}\subseteq N_{G^{\prime}}(v_{3})$),
then ${\cal O}_{2}={\cal O}_{2}(v_{1}v_{2},v_{3}v_{4})$ forms a graph $G$ by
adding to $G^{\prime}$ three new vertices $u_{0}$, $u_{1}$ and $u_{2}$ in such
a way that $u_{0}v_{1}v_{2}$, $v_{3}v_{4}u_{1}$, and $v_{3}u_{1}u_{2}$ are new
triangles, while
$R(G)=(R(G^{\prime})\setminus\\{v_{1}v_{2}v_{3}\\})\cup\\{u_{0}v_{1}v_{2},v_{3}u_{1}u_{2}\\}$
and $B(G)=B(G^{\prime})\cup\\{v_{1}v_{2}v_{3},v_{3}v_{4}u_{1}\\}$. In this
case we say that we apply the operation ${\cal O}_{2}$ to the edge
$v_{1}v_{2}$ of the triangle $v_{1}v_{2}v_{3}$ and to the edge $v_{3}v_{4}$.

The operations ${\cal O}_{1}$ and ${\cal O}_{2}$ are illustrated in Fig. 1.
Note that the operation ${\cal O}_{2}$ changes ’’colors‘‘ of certain
triangles, and the red triangle $v_{1}v_{2}v_{3}$ in $G^{\prime}$ is recolored
blue in $G$.

Figure 1: The operations ${\cal O}_{1}$ and ${\cal O}_{2}$

From the recursive definition of the graphs belonging to the family $\cal E$
it follows readily that if a $2$-tree $G$ belongs to $\cal E$, then the set
$R(G)$ of red triangles in $G$ is a perfect $3$-cover of $G$. From this and
from Proposition 2.2 it follows that $G$ is an $\alpha$-excellent graph. Thus
we have the following proposition that we will need when proving our main
theorem.

######  Proposition 3.1.

Every $2$-tree belonging to the family $\cal E$ has a perfect $3$-cover and it
is an $\alpha$-excellent graph.

The next theorem is the main result of this paper and it presents two
characterizations of the $\alpha$-excellent $2$-trees: a constructive
characterization, and a characterization in terms of perfect $3$-covers.

######  Theorem 3.2.

If $G$ is a $2$-tree of order $n\geq 3$, then the following statements are
equivalent:

  1. (a)

$G$ has a perfect $3$-cover.

  2. (b)

$G$ belongs to the family ${\cal E}$.

  3. (c)

$G$ is an $\alpha$-excellent graph.

###### Proof.

The implications $(\rm a)\Rightarrow(\rm c)$, $(\rm b)\Rightarrow(\rm a)$, and
$(\rm b)\Rightarrow(\rm c)$ are obvious from Propositions 2.2 and 3.1. Thus it
suffices to prove the implication $(\rm c)\Rightarrow(\rm b)$ (but we prove
the implications $(\rm c)\Rightarrow(\rm a)$ and $(\rm c)\Rightarrow(\rm b)$
at the same time).

Thus assume that $G$ is an $\alpha$-excellent $2$-tree of order at least $3$.
By induction on the order of $G$ we shall prove that $G$ has a perfect
$3$-cover and that $G$ belongs to the family $\cal E$. It is straightforward
to observe that the implications $(\rm c)\Rightarrow(\rm a)$ and $(\rm
c)\Rightarrow(\rm b)$ are true if $G$ is a $2$-tree of order $n\leq 6$. Now
let $G$ be an $\alpha$-excellent $2$-tree of order greater than $6$ and assume
that the implications $(\rm c)\Rightarrow(\rm a)$ and $(\rm c)\Rightarrow(\rm
b)$ are true for smaller $\alpha$-excellent $2$-trees. Let
$(T_{1},T_{2},\ldots,T_{p})$ be a longest $3$-path in $G$, that is, a longest
sequence $T_{1},T_{2},\ldots,T_{p}$ of triangles in $G$, where
$|V({T_{i}})\cap V({T_{j}})|=2$ if $|i-j|=1$, and $|V({T_{i}})\cap
V({T_{j}})|\leq 1$ if $|i-j|\geq 2$ ($i,j\in[p]$). From the fact that
$(T_{1},T_{2},\ldots,T_{p})$ is a longest $3$-path in $G$ (which is an
$\alpha$-excellent $2$-tree of order at least $7$) it follows that $p\geq 4$.
Assume that $a$, $b$, $c$, $d$, and $e$ are vertices of $G$ for which
$V({T_{p-3}})\cap V({T_{p-2}})=\\{a,b\\}$, $V({T_{p-2}})\setminus
V({T_{p-3}})=\\{c\\}$, $V({T_{p-1}})\setminus V({T_{p-2}})=\\{d\\}$, and
$V({T_{p}})\setminus V({T_{p-1}})=\\{e\\}$. From the choice of
$(T_{1},\ldots,T_{p})$, the vertex $e$ is of degree $2$ and $T_{p}$ is a
simplex in $G$. Let $G_{0}^{\prime},G_{1}^{\prime},\ldots,G_{\ell}^{\prime}$
be the components of $G-\\{a,b\\}$, where $G_{0}^{\prime}$ is that component
which contains at least one vertex of $T_{1}$. It is clear that $\ell$ is
positive integer.

We now let $G_{i}$ denote the subgraph of $G$ induced by
$V({G_{i}^{\prime}})\cup\\{a,b\\}$ for $i\in\\{0\\}\cup[\ell]$. Among the
graphs $G_{1},\ldots,G_{\ell}$, let $H$ be the graph that contains the
triangles of the $3$-path ${\cal P}_{0}=(T_{p-2},T_{p-1}^{0},$ $T_{p}^{0})$,
where $T_{p-1}^{0}=T_{p-1}$ and $T_{p}^{0}=T_{p}$. It is obvious that if
$T_{p-2}$, $T_{p-1}$, and $T_{p}$ are the only triangles of $H$, then it is
possible that $H$ is one of the graphs $H_{1}$, $H_{1}^{\prime}$, $H_{2}$, and
$H_{2}^{\prime}$ shown in Fig. 2. If $H$ contains the triangle $T_{p-2}$,
$T_{p-1}$, $T_{p}$ and a simplex $T_{p-1}^{\prime}$ that shares an edge with
the triangle $T_{p-2}$ in $H$, then it follows readily from Proposition 2.1
that $H$ is one of the graphs $H_{3}$ or $H_{3}^{\prime}$ in Fig. 2.

Figure 2: Graphs $H_{1}$, $H_{1}^{\prime}$, $H_{2}$, $H_{2}^{\prime}$,
$H_{3}$, and $H_{3}^{\prime}$

Thus assume that no simplex of $H$ shares an edge with the triangle $T_{p-2}$.
In this case, $H$ is a subgraph induced by the triangles belonging to ${\cal
P}_{0}$ and to some additional $3$-paths ${\cal
P}_{i}=(T_{p-2},T_{p-1}^{i},T_{p}^{i})$, where $i\in[n]$ and $n$ is a positive
integer. It follows from Proposition 2.1 that if $n=1$, then $H$ is isomorphic
to one of the graphs $H_{4}$, $H_{5}$ or $H_{6}$ in Fig. 3. Similarly, if
$n=2$, then, as can easily be verified, $H$ is isomorphic to the graph $H_{7}$
shown in Fig. 3. Finally, we claim that the case $n\geq 3$ is impossible.
Suppose, to the contrary, that $n\geq 3$. Then let us first observe that if
one of the edges $ac$ and $bc$ of the triangle $T_{p-2}$ belongs to at least
$3$ of the triangles $T_{p-1}^{0}=T_{p-1}$, $T_{p-1}^{1},\ldots,T_{p-1}^{n}$,
say to $T_{p-1}^{i},T_{p-1}^{j},T_{p-1}^{k}$ (where $0\leq i<j<k\leq n$), then
at least two of the simplexes $T_{p}^{i},T_{p}^{j},T_{p}^{k}$ of $H$ (and of
$G$) have a common vertex, which is impossible in an $\alpha$-excellent graph
$G$. Thus assume that neither $ac$ nor $bc$ belongs to three of the triangles
$T_{p-1}^{0}=T_{p-1}$, $T_{p-1}^{1},\ldots,T_{p-1}^{n}$. Then necessarily
$n=3$ and each of the edges $ac$ and $bc$ belongs to exactly two of the
triangles $T_{p-1}^{0},T_{p-1}^{1},T_{p-1}^{2},T_{p-1}^{3}$, say $ac$ belongs
to $T_{p-1}^{0}$ and $T_{p-1}^{1}$, while $bc$ belongs to $T_{p-1}^{2}$ and
$T_{p-1}^{3}$. Therefore, as it is easy to verify, if neither the simplexes
$T_{p}^{0}$ and $T_{p}^{1}$ have a common vertex nor the simplexes $T_{p}^{2}$
and $T_{p}^{3}$ have a common vertex, then one of the simplexes $T_{p}^{0}$
and $T_{p}^{1}$ has a common vertex with one of the simplexes $T_{p}^{2}$ and
$T_{p}^{3}$, which again by Proposition 2.1 is impossible as $G$ is an
$\alpha$-excellent graph. This proves that the case $n\geq 3$ is impossible.

Figure 3: Graphs $H_{4}$, $H_{5}$, $H_{6}$, and $H_{7}$

There are now several cases to consider depending on the structure of $H$. We
begin showing that $H$ cannot be any of the graphs $H_{1}$, $H_{1}^{\prime}$,
$H_{4}$. Suppose, to the contrary, that $H=H_{1}$ (where $H_{1}$ is as
illustrated in Fig. 2). Then, since $G$ is an $\alpha$-excellent graph, there
exists an $\alpha$-set $I$ in $G$ that contains $a$. However in this case,
$(I\setminus\\{a\\})\cup\\{c,e\\}$ is an independent set in $G$, and so
$\alpha(G)\geq|(I\setminus\\{a\\})\cup\\{c,e\\}|>|I|=\alpha(G)$, a
contradiction which proves that $H\neq H_{1}$. Analogously, $H\neq
H_{1}^{\prime}$. Similarly, suppose that $H=H_{4}$ (where $H_{4}$ is shown in
Fig. 3). Let $I_{d}$ be an $\alpha$-set that contains $d$ in $G$. We note that
$|I_{d}\cap\\{b,f,g\\}|=1$. If $b\in I_{d}$, then let
$I_{d}^{\prime}=(I_{d}\setminus\\{b,d\\})\cup\\{c,e,g\\}$. If $f\in I_{d}$,
then let $I_{d}^{\prime}=(I_{d}\setminus\\{d,f\\})\cup\\{c,e,g\\}$. If $g\in
I_{d}$, then let $I_{d}^{\prime}=(I_{d}\setminus\\{d\\})\cup\\{c,e\\}$. In all
cases, the resulting set $I_{d}^{\prime}$ is an independent set in $G$, and so
$\alpha(G)\geq|I_{d}^{\prime}|>|I_{d}|=\alpha(G)$, a contradiction. Hence,
$H\neq H_{4}$.

In each of the next five cases (corresponding to the possible graphs $H$, that
is, to the graphs $H_{2}$ (and $H_{2}^{\prime}$), $H_{3}$, $H_{5}$, $H_{6}$,
and $H_{7}$) we prove that $G$ belongs to the family $\cal E$ and has a
perfect $3$-cover.

_Case 1. $H=H_{2}$ or $H=H_{2}^{\prime}$._ Without loss of generality, assume
that $H=H_{2}$ (see Fig. 2). In this case, let $G^{\prime}$ denote the
subgraph $G-\\{c,d,e\\}$ of $G$. In the next three claims we explain the main
relations between properties of the graphs $G$ and $G^{\prime}$, that is, we
prove that: (1) $\alpha(G^{\prime})=\alpha(G)-1$; (2) $G^{\prime}$ is an
$\alpha$-excellent graph; (3) $G$ has a perfect $3$-cover and belongs to the
family $\cal E$.

_Claim 1.1._ $\alpha(G^{\prime})=\alpha(G)-1$.

If $I^{\prime}$ is an $\alpha$-set of $G^{\prime}$, then
$I^{\prime}\cup\\{e\\}$ is an independent set in $G$ (as $N_{G}[e]\cap
I^{\prime}=\\{c,d,e\\}\cap I^{\prime}=\emptyset$) and therefore
$\alpha(G)\geq|I^{\prime}\cup\\{e\\}|=\alpha(G^{\prime})+1$. On the other
hand, let $I$ be an $\alpha$-set of $G$. In this case, $|I\cap\\{c,d,e\\}|=1$
and $I\setminus\\{c,d,e\\}$ is independent in $G^{\prime}$. Thus,
$\alpha(G^{\prime})\geq|I\setminus\\{c,d,e\\}|=|I|-1=\alpha(G)-1$.
Consequently, $\alpha(G^{\prime})=\alpha(G)-1$.

_Claim 1.2._ $G^{\prime}$ is an $\alpha$-excellent graph.

Let $v$ be an arbitrary vertex of $G^{\prime}$. We show that $v$ belongs to an
$\alpha$-set of $G^{\prime}$. Since $\alpha(G^{\prime})=\alpha(G)-1$ (by Claim
1.1), it suffices to show that $v$ belongs to an independent set of
cardinality $\alpha(G)-1=\alpha(G^{\prime})$ in $G^{\prime}$. Let $I_{v}$ be
an $\alpha$-set of $G$ that contains $v$, and let $I_{v}^{\prime}$ denote the
set $I_{v}\setminus\\{c,d,e\\}$. Thus, $v\in I_{v}^{\prime}$ and the set
$I_{v}^{\prime}$ is independent in $G^{\prime}$. Furthermore, $I_{v}^{\prime}$
is an $\alpha$-set of $G^{\prime}$ noting that $|I_{v}\cap\\{c,d,e\\}|=1$ and
$|I_{v}^{\prime}|=|I_{v}\setminus\\{c,d,e\\}|=|I_{v}|-1=\alpha(G)-1=\alpha(G^{\prime})$.
This proves that $G^{\prime}$ is an $\alpha$-excellent graph.

_Claim 1.3._ $G$ has a perfect $3$-cover and $G$ belongs to the family $\cal
E$.

By Claim 1.2, $G^{\prime}$ is an $\alpha$-excellent graph. Since the order of
$G^{\prime}$ is less than the order of $G$, applying the induction hypothesis
we infer that $G^{\prime}$ has a perfect $3$-cover and $G^{\prime}$ belongs to
the family $\cal E$. Now, if ${\cal P}^{\prime}$ is a perfect $3$-cover of
$G^{\prime}$, then ${\cal P}^{\prime}\cup\\{cde\\}$ is a perfect $3$-cover of
$G$. In addition, since $G^{\prime}$ belongs to the family $\cal E$, the graph
$G^{\prime}$ can be obtained recursively from a red triangle by operations
${\cal O}_{1}$ and ${\cal O}_{2}$, and, since $G$ can be obtained from
$G^{\prime}$ by the operation ${\cal O}_{1}={\cal O}_{1}(a,b)$ (that is, by
${\cal O}_{1}$ applied to the edge $ab$ of $G^{\prime}$), the graph $G$ can be
obtained recursively from a red triangle by operations ${\cal O}_{1}$ and
${\cal O}_{2}$. Thus, $G$ belongs to the family $\cal E$.

_Case 2. $H=H_{3}$ or $H=H_{3}^{\prime}$._ Without loss of generality, assume
that $H=H_{3}$ (see Fig. 2). This time, let $G^{\prime}$ denote the subgraph
$G-\\{d,e,f\\}$ of $G$. As in Case 1, we study desired relations between
properties of the graphs $G$ and $G^{\prime}$.

_Claim 2.1._ $\alpha(G^{\prime})=\alpha(G)-1$.

Let $I^{\prime}$ be an $\alpha$-set of $G^{\prime}$. In this case,
$|I^{\prime}\cap\\{a,b,c\\}|=1$ and either $a\in I^{\prime}$ or $\\{b,c\\}\cap
I^{\prime}\neq\emptyset$. Consequently, either $I^{\prime}\cup\\{f\\}$ or
$I^{\prime}\cup\\{e\\}$ is an independent set in $G$, respectively, and
therefore
$\alpha(G)\geq|I^{\prime}\cup\\{f\\}|=|I^{\prime}\cup\\{e\\}|=\alpha(G^{\prime})+1$.
This proves that $\alpha(G)\geq\alpha(G^{\prime})+1$. Now, let $I$ be an
$\alpha$-set of $G$. Then $|I\cap\\{a,b,c\\}|\leq 1$ and we consider four
cases. If $I\cap\\{a,b,c\\}=\emptyset$, then $|I\cap\\{d,e,f\\}|=2$ and
$(I\setminus\\{d,e,f\\})\cup\\{c\\}$ is an independent set of cardinality
$\alpha(G)-1$ in $G^{\prime}$. If $a\in I$, then $f\in I$, and
$I\setminus\\{f\\}$ is an independent set of cardinality $\alpha(G)-1$ in
$G^{\prime}$. If $b\in I$, then $|I\cap\\{d,e\\}|=1$, $f\notin I$, and
$I\setminus\\{d,e\\}$ is an independent set of cardinality $\alpha(G)-1$ in
$G^{\prime}$. If $c\in I$, then $e\in I$, $f\notin I$, and $I\setminus\\{e\\}$
is an independent set of cardinality $\alpha(G)-1$ in $G^{\prime}$.
Consequently, $\alpha(G^{\prime})\geq\alpha(G)-1$. This proves that
$\alpha(G^{\prime})=\alpha(G)-1$.

_Claim 2.2._ $G^{\prime}$ is an $\alpha$-excellent graph.

Let $v$ be an arbitrary vertex of $G^{\prime}$. As in the proof of Claim 1.2,
it suffices to show that $v$ belongs to an $\alpha$-set of $G^{\prime}$, that
is, to an independent set of cardinality $\alpha(G^{\prime})=\alpha(G)-1$ in
$G^{\prime}$. Since $G$ is $\alpha$-excellent, every vertex of $G$ belongs to
some $\alpha$-set in $G$. Let $I_{x}$ be an $\alpha$-set of $G$ that contains
$x$, where $x\in V(G)$. We note that $I_{a}\cap\\{d,e,f\\}=\\{f\\}$ and,
consequently, $I_{a}\setminus\\{f\\}$ is an $\alpha$-set of $G^{\prime}$ that
contains the vertex $a$. Similarly, $I_{b}\setminus\\{d,e\\}$ and
$I_{c}\setminus\\{e\\}$ are $\alpha$-sets of $G^{\prime}$ and they contain $b$
and $c$, respectively. If $v\in V({G^{\prime}})\setminus\\{a,b,c\\}$ and
$I_{v}\cap\\{a,b,c\\}=\emptyset$, then $|I_{v}\cap\\{d,e,f\\}|=2$ and
$(I_{v}\setminus\\{d,e,f\\})\cup\\{c\\}$ is an $\alpha$-set of $G^{\prime}$
and it contains $v$. Finally, if $v\in V({G^{\prime}})\setminus\\{a,b,c\\}$
and $I_{v}\cap\\{a,b,c\\}\neq\emptyset$, then $|I_{v}\cap\\{a,b,c\\}|=1$,
$|I_{v}\cap\\{d,e,f\\}|=1$, and, therefore, $I_{v}\setminus\\{d,e,f\\}$ is an
$\alpha$-set of $G^{\prime}$ and it contains $v$. Consequently, $G^{\prime}$
is an $\alpha$-excellent graph.

_Claim 2.3._ $G$ has a perfect $3$-cover and $G$ belongs to the family $\cal
E$.

Now, similarly as in the proof of Claim 1.3, since $G^{\prime}$ is an
$\alpha$-excellent graph of order less than the order of $G$, the induction
hypothesis implies that $G^{\prime}$ has a perfect $3$-cover and that
$G^{\prime}$ belongs to the family $\cal E$. Certainly, if ${\cal P}^{\prime}$
is a perfect $3$-cover of $G^{\prime}$, then $abc\in{\cal P}^{\prime}$ and
$({\cal P}^{\prime}\setminus\\{abc\\})\cup\\{ade,bcf\\}$ is a perfect
$3$-cover of $G$. In addition, since $G^{\prime}$ belongs to the family $\cal
E$, the graph $G^{\prime}$ can be obtained recursively from a red triangle by
operations ${\cal O}_{1}$ and ${\cal O}_{2}$. From this and from the obvious
fact that $G$ can be obtained from $G^{\prime}$ by the operation ${\cal
O}_{2}={\cal O}_{2}(bc,ac)$ (that is, by ${\cal O}_{2}$ applied to the edge
$bc$ of the simplex $abc$ of $G^{\prime}$ and to the edge $ac$ incident with
the third vertex $c$ of the triangle $abc$), the graph $G$ can be obtained
recursively from a red triangle by operations ${\cal O}_{1}$ and ${\cal
O}_{2}$. Thus, $G$ belongs to the family $\cal E$.

_Case 3. $H=H_{5}$._ In this case, we let $G^{\prime}$ denote the subgraph
$G-\\{e,f,g\\}$ of $G$ and, as before, we study desired relations between
properties of the graphs $G$ and $G^{\prime}$.

_Claim 3.1._ $\alpha(G^{\prime})=\alpha(G)-1$.

Let $I^{\prime}$ be an $\alpha$-set of $G^{\prime}$. In this case,
$|I^{\prime}\cap\\{a,c,d\\}|=1$. If $a\in I^{\prime}$ or $d\in I^{\prime}$,
then the set $I^{\prime}\cup\\{g\\}$ is an independent set of $G$, while if
$c\in I^{\prime}$, then the set $I^{\prime}\cup\\{e\\}$ is an independent set
of $G$, implying that $\alpha(G)\geq\alpha(G^{\prime})+1$. It remains to prove
that $\alpha(G^{\prime})\geq\alpha(G)-1$. To prove this, let $I$ be an
$\alpha$-set of $G$. Thus, $|I\cap\\{a,d,e\\}|=1$ and $|I\cap\\{c,f,g\\}|=1$.
If $a\in I$ or $d\in I$, then $|I\cap\\{f,g\\}|=1$ and we let
$I^{\prime}=I\setminus\\{f,g\\}$. If $e\in I$ and $c\in I$, then we let
$I^{\prime}=I\setminus\\{e\\}$. If $e\in I$ and $b\in I$, then $g\in I$ and we
let $I^{\prime}=(I\setminus\\{e,g\\})\cup\\{d\\}$. If $e\in I$ and
$I\cap\\{b,c\\}=\emptyset$, then $|I\cap\\{f,g\\}|=1$ and we let
$I^{\prime}=(I\setminus\\{e,f,g\\})\cup\\{c\\}$. In all the above cases, the
set $I^{\prime}$ is an independent set in $G^{\prime}$ and
$|I^{\prime}|=|I|-1$, implying that
$\alpha(G^{\prime})\geq|I^{\prime}|=|I|-1=\alpha(G)-1$. As observed earlier,
$\alpha(G^{\prime})\leq\alpha(G)-1$. Consequently,
$\alpha(G^{\prime})=\alpha(G)-1$.

_Claim 3.2._ $G^{\prime}$ is an $\alpha$-excellent graph.

Since $G$ is an $\alpha$-excellent graph, every vertex of $G$ belongs to an
$\alpha$-set of $G$. Let $I_{x}$ denote an $\alpha$-set of $G$ that contains
the vertex $x$ of $G$. Let $v$ be an arbitrary vertex of $G^{\prime}$. We show
that $v$ belongs to an $\alpha$-set of $G^{\prime}$, that is, to an
independent set of cardinality $\alpha(G^{\prime})=\alpha(G)-1$ in
$G^{\prime}$. We note that $|I_{v}\cap\\{a,d,e\\}|=1$,
$|I_{v}\cap\\{c,f,g\\}|=1$, and $|I_{v}\cap\\{a,b,c,d\\}|\in\\{0,1,2\\}$. If
$|I_{v}\cap\\{a,b,c,d\\}|=2$, then $I_{v}\cap\\{a,b,c,d\\}=\\{b,d\\}$, $g\in
I_{v}$ and we let $I_{v}^{\prime}=I_{v}\setminus\\{g\\}$. If
$I_{v}\cap\\{a,b,c,d\\}=\emptyset$, then $e\in I_{v}$ and
$|I_{v}\cap\\{f,g\\}|=1$ and we let
$I_{v}^{\prime}=(I_{v}\setminus\\{e,f,g\\})\cup\\{c\\}$. If
$I_{v}\cap\\{a,b,c,d\\}=\\{a\\}$ or $I_{v}\cap\\{a,b,c,d\\}=\\{d\\}$, then
$|I_{v}\cap\\{f,g\\}|=1$ and we let $I_{v}^{\prime}=I_{v}\setminus\\{f,g\\}$.
If $I_{v}\cap\\{a,b,c,d\\}=\\{b\\}$, then $e\in I_{v}$, $g\in I_{v}$, and we
let $I_{v}^{\prime}=(I_{v}\setminus\\{e,g\\})\cup\\{d\\}$. If
$I_{v}\cap\\{a,b,c,d\\}=\\{c\\}$, then $e\in I_{v}$ and we let
$I_{v}^{\prime}=I_{v}\setminus\\{e\\}$. In all cases, the set $I_{v}^{\prime}$
is an independent set in $G^{\prime}$ that contains the vertex $v$ and
$|I_{v}^{\prime}|=|I_{v}|-1=\alpha(G)-1=\alpha(G^{\prime})$, implying that $v$
belongs to an $\alpha$-set of $G^{\prime}$, as desired.

_Claim 3.3._ $G$ has a perfect $3$-cover and $G$ belongs to the family $\cal
E$.

Similarly as in the proofs of Claims 1.3 and 2.3, since $G^{\prime}$ is an
$\alpha$-excellent graph of order less than the order of $G$, the induction
hypothesis implies that $G^{\prime}$ has a perfect $3$-cover and that
$G^{\prime}$ belongs to the family $\cal E$. Now, if ${\cal P}^{\prime}$ is a
perfect $3$-cover of $G^{\prime}$, then $acd\in{\cal P}^{\prime}$ and $({\cal
P}^{\prime}\setminus\\{acd\\})\cup\\{ade,cfg\\}$ is a perfect $3$-cover of
$G$. In addition, since $G^{\prime}$ belongs to the family $\cal E$, the graph
$G^{\prime}$ can be obtained recursively from a red triangle by operations
${\cal O}_{1}$ and ${\cal O}_{2}$, and, since $G$ can be obtained from
$G^{\prime}$ by the operation ${\cal O}_{2}={\cal O}_{2}(ad,cb)$ (that is, by
${\cal O}_{2}$ applied to the edge $ad$ of the simplex $acd$ of $G^{\prime}$
and to the edge $cb$ incident with the third vertex $c$ of the triangle
$acd$), the graph $G$ can be obtained recursively from a red triangle by
operations ${\cal O}_{1}$ and ${\cal O}_{2}$. Thus, $G$ belongs to the family
$\cal E$.

_Case 4. $H=H_{6}$._ In this case, we let $G^{\prime}$ denote the subgraph
$G-\\{e,f,g\\}$ of $G$ and, as before, we study desired relations between
properties of the graphs $G$ and $G^{\prime}$.

_Claim 4.1._ $\alpha(G^{\prime})=\alpha(G)-1$.

Let $I^{\prime}$ be an $\alpha$-set of $G^{\prime}$. In this case,
$|I^{\prime}\cap\\{b,c,d\\}|=1$. If $c\in I^{\prime}$ or $d\in I^{\prime}$,
then the set $I^{\prime}\cup\\{g\\}$ is an independent set of $G$, while if
$b\in I^{\prime}$, then the set $I^{\prime}\cup\\{e\\}$ is an independent set
of $G$, implying that $\alpha(G)\geq\alpha(G^{\prime})+1$. It remains to prove
that $\alpha(G^{\prime})\geq\alpha(G)-1$. By supposition, $G$ is an
$\alpha$-excellent graph, and so every vertex of $G$ belongs to some
$\alpha$-set of $G$. Let $I$ be an $\alpha$-set of $G$ that contains the
vertex $c$. Necessarily, $g\in I$ and $\\{b,e,f\\}\cap I=\emptyset$. Thus,
$I\setminus\\{g\\}$ is an independent set in $G^{\prime}$, implying that
$\alpha(G^{\prime})\geq|I|-1=\alpha(G)-1$. As observed earlier,
$\alpha(G^{\prime})\leq\alpha(G)-1$. Consequently,
$\alpha(G^{\prime})=\alpha(G)-1$.

_Claim 4.2._ $G^{\prime}$ is an $\alpha$-excellent graph.

Since $G$ is an $\alpha$-excellent graph, every vertex of $G$ belongs to an
$\alpha$-set of $G$. Let $I_{x}$ denote an $\alpha$-set of $G$ that contains
the vertex $x$ of $G$. Let $v$ be an arbitrary vertex of $G^{\prime}$. We show
that $v$ belongs to an $\alpha$-set of $G^{\prime}$, that is, to an
independent set of cardinality $\alpha(G^{\prime})=\alpha(G)-1$ in
$G^{\prime}$. This time we note that $|I_{v}\cap\\{c,d,e\\}|=1$,
$|I_{v}\cap\\{b,f,g\\}|=1$, and $|I_{v}\cap\\{a,b,c,d\\}|\in\\{0,1,2\\}$. If
$|I_{v}\cap\\{a,b,c,d\\}|=2$ (that is, if $I_{v}\cap\\{a,b,c,d\\}=\\{a,d\\}$)
or $I_{v}\cap\\{a,b,c,d\\}=\\{d\\}$, then $|I_{v}\cap\\{f,g\\}|=1$ and we let
$I_{v}^{\prime}=I_{v}\setminus\\{f,g\\}$. If
$I_{v}\cap\\{a,b,c,d\\}=\emptyset$ or $I_{v}\cap\\{a,b,c,d\\}=\\{a\\}$, then
$e\in I_{v}$, $|I_{v}\cap\\{f,g\\}|=1$ and we let
$I_{v}^{\prime}=(I_{v}\setminus\\{e,f,g\\})\cup\\{d\\}$. If
$I_{v}\cap\\{a,b,c,d\\}=\\{b\\}$, then $e\in I_{v}$ and we let
$I_{v}^{\prime}=I_{v}\setminus\\{e\\}$. If $I_{v}\cap\\{a,b,c,d\\}=\\{c\\}$,
then $g\in I_{v}$ and we let $I_{v}^{\prime}=I_{v}\setminus\\{g\\}$. In all
cases, the set $I_{v}^{\prime}$ is an independent set in $G^{\prime}$ that
contains the vertex $v$ and
$|I_{v}^{\prime}|=|I_{v}|-1=\alpha(G)-1=\alpha(G^{\prime})$, implying that $v$
belongs to an $\alpha$-set of $G^{\prime}$, as desired.

_Claim 4.3._ $G$ has a perfect $3$-cover and $G$ belongs to the family $\cal
E$.

Similarly as in the proofs of Claims 1.3, 2.3 and 3.3, since $G^{\prime}$ is
an $\alpha$-excellent graph of order less than the order of $G$, the induction
hypothesis implies that $G^{\prime}$ has a perfect $3$-cover and that
$G^{\prime}$ belongs to the family $\cal E$. Now, if ${\cal P}^{\prime}$ is a
perfect $3$-cover of $G^{\prime}$, then $bcd\in{\cal P}^{\prime}$ and $({\cal
P}^{\prime}\setminus\\{bcd\\})\cup\\{cde,bfg\\}$ is a perfect $3$-cover of
$G$. In addition, since $G^{\prime}$ belongs to the family $\cal E$, the graph
$G^{\prime}$ can be obtained recursively from a red triangle by operations
${\cal O}_{1}$ and ${\cal O}_{2}$, and, since $G$ can be obtained from
$G^{\prime}$ by the operation ${\cal O}_{2}={\cal O}_{2}(cd,bc)$ (that is, by
${\cal O}_{2}$ applied to the edge $cd$ of the simplex $bcd$ of $G^{\prime}$
and to the edge $bc$ incident with the third vertex $b$ of the triangle
$bcd$), the graph $G$ can be obtained recursively from a red triangle by
operations ${\cal O}_{1}$ and ${\cal O}_{2}$. Thus, $G$ belongs to the family
$\cal E$.

_Case 5. $H=H_{7}$._ In this case, we let $G^{\prime}$ denote the subgraph
$G-\\{e,f,g\\}$ of $G$. Using identical arguments as in the proof of Case 4,
we prove that $G$ has a perfect $3$-cover and it belongs to the family $\cal
E$. We omit the details.

Thus all possible cases have been considered. This completes the proof of
Theorem 3.2. ∎

It is easy to observe that the corona graph $H\circ K_{1}$ (the graph formed
from $H$ by adding for each vertex $v$ in $H$ a new vertex $v^{\prime}$ and
the edge $vv^{\prime}$) is an $\alpha$-excellent graph for every graph $H$.
This implies that every graph is an induced subgraph of an $\alpha$-excellent
graph. As a consequence of Theorem 3.2, we have the following property of
$2$-trees.

######  Corollary 3.3.

Every $2$-tree is an induced subgraph of an $\alpha$-excellent $2$-tree.

###### Proof.

Let $G$ be a $2$-tree and let $\cal P$ be a family of vertex-disjoint
triangles of $G$. Let $Q$ be the set of all vertices in $G$ that do not belong
to any triangle in ${\cal P}$. If the set $Q$ is empty, then, by Theorem 3.2,
$G$ is an $\alpha$-excellent $2$-tree itself (and, therefore, it has the
desired property). Thus assume that $Q$ is nonempty. For each vertex $v\in Q$,
we do the following. Let $v^{\prime}$ be an arbitrary neighbor of $v$ in $G$.
We now add two new vertices $x_{vv^{\prime}}$ and $y_{vv^{\prime}}$, and four
edges $x_{vv^{\prime}}v$, $x_{vv^{\prime}}v^{\prime}$, $y_{vv^{\prime}}v$ and
$y_{vv^{\prime}}x_{vv^{\prime}}$. We note that the newly constructed triangle
$vx_{vv^{\prime}}y_{vv^{\prime}}$ covers the vertex $v$ and the two new
vertices $x_{vv^{\prime}}$ and $y_{vv^{\prime}}$. Let $G^{\prime}$ be a
resulting $2$-tree obtained from $G$ by performing this operation for all
vertices $v\in Q$. Then the set ${\cal P}\cup\bigcup_{v\in
Q}\\{vx_{vv^{\prime}}y_{vv^{\prime}}\\}$ is a perfect $3$-cover of
$G^{\prime}$. Thus, by Theorem 3.2, the graph $G^{\prime}$ is an
$\alpha$-excellent $2$-tree. By construction, the $2$-tree $G$ is an induced
subgraph of the $\alpha$-excellent $2$-tree $G^{\prime}$. This completes the
proof of Corollary 3.3. ∎

We close this paper with the following open question that we have yet to
settle: Is it true that if $k\geq 3$ is an integer and $G$ is an
$\alpha$-excellent $k$-tree of order at least $k+1$, then $G$ has a perfect
$(k+1)$-cover?

## References

  * [1] C. Berge, Theory of Graphs and its Applications, Methuen, London, 1962.
  * [2] C. Berge, Some common properties for regularisable graphs, edge-critical graphs and $B$-graphs. In: N. Saito, T. Nishiezeki (eds), Graph Theory and Algorithms. Lecture Notes in Comput. Sci., 108, Springer, New York, 1981, 108–123.
  * [3] C. Berge, Graphs, North-Holland, Amsterdam, 1985.
  * [4] M. Dettlaff, M.A. Henning, J. Topp, On $\alpha$-excellent graphs, arXiv:2208.08498.
  * [5] M. Dettlaff, M. Lemańska, J. Topp, Common independence in graphs, Symmetry 13 (2021) 1411. https://doi.org/10.3390/sym13081411
  * [6] G.S. Domke, J.H. Hatting, L.R. Markus, On weakly connected domination in graphs II, Discrete Math. 305 (2005) 112–122.
  * [7] G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, Excellent trees, Bull. Inst. Combin. Appl. 34 (2002) 27–38.
  * [8] W. Goddard, M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854.
  * [9] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Topics in Domination in Graphs. Developments in Mathematics, 64, Springer, Cham, 2020. DOI 10.1007/978-3-030-51117-3.
  * [10] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Structures of Domination in Graphs. Developments in Mathematics, 66, Springer, Cham, 2021. DOI 10.1007/978-3-030-58892-2.
  * [11] T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in Graphs: Core Concepts. Springer Monographs in Mathematics, Springer, Cham, 2022. DOI 9783031094958.
  * [12] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38, Providence, RI, 1962.
  * [13] M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91–98.
  * [14] M.D. Plummer, Well-covered graphs: a survey, Quaestiones Math. 16 (1993) 253–287.
  * [15] A.P. Pushpalatha, G. Jothilakshmi, S. Suganathi, V. Swaminathan, $\beta_{0}$-excellent graphs, Int. J. Contemp. Math. Sciences 6 (2011) 1447–1451.
  * [16] A.P. Pushpalatha, G. Jothilakshmi, S. Suganathi, V. Swaminathan, Very $\beta_{0}$-excellent graphs, Taga Journal 14 (2018) 144–148. (https://www.tagajournal.com/gallery/v14.15.pdf)
  * [17] D.J. Rose, On simple characterizations of $k$-trees, Discrete Math. 7 (1974) 317–322.
  * [18] J. Topp, Domination, independence and irredundance in graphs, Dissertationes Math. 342 (1995) 99 pp.