1. Introduction
Let G be a simple finite graph and
be two vertices of G. We use
to denote the distance, or the shortest length of paths between
and
,
to denote the set of vertices adjacent to
and
. Furthermore, we use
or
to denote the cardinality of
.
Given a finite simple graph G, a set
is called a dominating set if for all
, either
or
is adjacent to some vertex in D. For a graph G, the domination number is the size of the smallest possible dominating set. A dominating set D is independent if none of the vertices in D are adjacent and perfect if each vertex not in D is adjacent to precisely one vertex in D. If a dominating set is both independent and perfect, then it is called an efficient dominating set. Another way to define efficient dominating sets is to state that a vertex dominates its neighbors and itself when it is in the dominating set. Using this convention, an efficient dominating set is a dominating set that dominates every vertex in a graph exactly once. For a graph G, a set D is called a unique efficient dominating set of G if it is the only efficient dominating set of G.
The following theorem, which was proved in [1], establishes the fact that an efficient dominating set is also a minimum dominating set.
Theorem 1.1. If G has an efficient dominating set, then the cardinality of any efficient dominating set equals the domination number. In particular, all efficient dominating sets of G have the same cardinality.
The following lemma applies to all nontrivial efficient dominating sets.
Lemma 1.2. Let D be a nontrivial efficient dominating set of G. Then the following statements are true.
i) For any two vertices
,
.
ii) For any vertex
, there exists a vertex
such that
.
iii)
is the disjoint union of all
, where
and
.
iv) If
and
, then either
or
. Furthermore, if
, then
.
v) If
and
, then
.
vi) If
and
, then
.
Proof. i) It follows directly from the fact that an efficient dominating set is independent and perfect.
ii) Let
and
. Since D is independent and perfect,
and
. This implies that the vertices in
are dominated by one or more vertices other than
. Let
be one of these vertices. Then it follows that
.
iii) For any
, if
, there is a unique vertex
such that
is dominated by
. That is to say, there is a unique vertex
such that
. Therefore,
is the disjoint union of
for all the
and so iii) follows.
iv) Since D is an efficient dominating set of G and
, it follows that either
or
. If
, then
and
. By i),
.
v) Suppose that
. Since
and
,
and
, which contradicts iv). Therefore,
and by iv),
.
vi) Let
be a path of G. If
, then
. By i),
and
. So
is not dominated by any vertex in D, a contradiction. Therefore,
and similarly
.
Lemma 1.3. Suppose that
is a path with
. Let D be an efficient dominating set of G. If
, then
.
Proof. By Lemma 1.2 i),
and
. By the fact that H is a path with
,
. Otherwise,
is not dominated by any vertex in D.
In Section 2, the authors study operations on graphs with unique efficient dominating sets that generate new graphs with unique efficient dominating sets. In Section 3.1, the authors characterize the paths, cycles, and tadpole graphs which have unique efficient dominating sets. In Section 3.2, the authors prove that star/sunlet/centipede/firecracker graphs all have unique efficient dominating sets, and they characterize all the caterpillar graphs which have unique efficient dominating sets. In Section 3.3, the authors investigate spider graphs and fully characterize the spider graphs which have unique efficient dominating sets.
2. Properties of Unique Efficient Dominating Sets
The following two results are based on [2].
Theorem 2.1. Let
and
be two graphs with unique efficient dominating sets
and
, respectively. Let
and
be two vertices in
and
, respectively. If G is the graph obtained from
by connecting
and
with an edge, that is,
, then
is the unique efficient dominating set of G.
Proof. Since for
,
is the unique efficient dominating set of
,
is an efficient dominating set of G. Suppose that there exists an efficient dominating set
of G. Suppose that
. Then
is an efficient dominating set of
. Since
and
,
, contradicting the fact that
has a unique efficient dominating set. Therefore,
and similarly
. Thus, for
,
is dominated by a vertex of
and so
is an efficient dominating set of
. Since
is the unique efficient dominating set of
,
. So
. Hence,
is the unique efficient dominating set of G.
Theorem 2.2. Let
and
be two graphs with unique efficient dominating sets
and
, respectively. Let
and
. If G is the graph obtained from
by adding two new vertices
and
, and three edges
,
and
, then
is the unique efficient dominating set of G.
Proof. Since for
,
is the unique efficient dominating set of
,
is an efficient dominating set of G. Suppose that G has another efficient dominating set
. Suppose that
. Since
is dominated by
,
. Then
is an efficient dominating set of
with
. Since
,
, contradicting the fact that
is a unique efficient dominating set of
. Hence,
and similarly
. In order to ensure that
and
are dominated, it is the case that
and
. So for
,
is an efficient dominating set of
. Since
is the unique efficient dominating set of
,
and so
. Hence,
is the unique efficient dominating set of G.
The following theorem describes when identifying vertices results in a graph with a unique efficient dominating set.
Theorem 2.3. Let
and
be two graphs with unique efficient dominating sets
and
, respectively. Let
and
. If G is the graph obtained from
by identifying
and
as a single vertex
, then
is the unique efficient dominating set of G.
Proof. Since for
,
is the unique efficient dominating set of
,
is an efficient dominating set of G. Let
be another efficient dominating set of G. Suppose that
, and without loss of generality, suppose that
is dominated by a vertex in
. Then
is an efficient dominating set of
. Since
and
,
, contradicting the fact that
has a unique efficient dominating set. Thus,
, and
is an efficient dominating set of
. Since
is the unique efficient dominating set of
,
and so
. Hence,
is the unique efficient dominating set of G.
The following two theorems are special ways to identify vertices involving pendent vertices.
Theorem 2.4. Let
and
be two graphs with unique efficient dominating sets
and
, respectively. Let
and
be two pendant vertices such that
and
. Denote the neighbors of
and
as
and
, respectively. If G is the graph obtained from
by identifying
and
as a single vertex
and by identifying
and
as a single vertex
, then G has the unique efficient dominating set
.
Proof. Since for
,
is the unique efficient dominating set of
,
is an efficient dominating set of G. Suppose that G has another efficient dominating set
. Since
and
, by Lemma 1.2 iv),
or
. Suppose that
. Then for
,
is an efficient dominating set of
. Since
but
,
, contradicting the fact that
has a unique efficient dominating set. So
and then
. Now
is an efficient dominating set of
. Since
is the unique efficient dominating set of
,
and so
. Hence,
is the unique efficient dominating set of G.
Theorem 2.5. Let
and
be two graphs with unique efficient dominating sets
and
, respectively. Let
and
be two pendant vertices with neighbors
and
such that
and
. If G is the graph obtained by identifying
and
as a single vertex
and by identifying
and
as a single vertex
, then G has the unique efficient dominating set
.
Proof. Since for
,
is the unique efficient dominating set of
,
is an efficient dominating set of G. Suppose that G has another efficient dominating set
. Since
and
, by Lemma 1.2 iv),
or
. Suppose that
. Then for
,
is an efficient dominating set of
. Since
but
,
, contradicting the fact that
has a unique efficient dominating set. So
and then
. Now
is an efficient dominating set of
. Since
is the unique efficient dominating set of
,
and so
. Hence,
is the unique efficient dominating set of G.
Theorem 2.6. Suppose that
is a path with
. Let
be a graph obtained from G by deleting
and connecting
and
. Then G has a unique efficient dominating set if and only if
has a unique efficient dominating set.
Proof. Suppose that D is an efficient dominating set of G. If
, then by Lemma 1.2 i),
and
. In this case,
is an efficient dominating set of
. If
, then either
or
. Without loss of generality, suppose that
. By Lemma 1.3,
. Since
and
(since
),
is an efficient dominating set of
with
dominating
.
Suppose that
is an efficient dominating set of
. If
and
, then
is an efficient dominating set of G. If
or
, say
, then
is an efficient dominating set of G.
The above proof shows that there is a one-to-one correspondence between the efficient dominating sets of G and the efficient dominating sets of
. Therefore, G has a unique efficient dominating set if and only if
has a unique efficient dominating set.
3. Graphs with Unique Efficient Dominating Sets
In this section, the authors investigate several families of graphs to determine the conditions which guarantee the existence of unique efficient dominating sets.
3.1. Paths, Cycles and Tadpole Graphs
For a positive integer n, denote the path with n vertices by
.
Lemma 3.1. If
, then the following conclusions are true.
1) If
, then G has a unique efficient dominating set.
2) If
, then G has a unique efficient dominating set.
3) If
, then G has two efficient dominating sets.
Proof. Suppose that D is an efficient dominating set of G.
1) The path
has a unique efficient dominating set
, and any path
such that
can be constructed from copies of
by connecting the vertices on the ends. By Theorem 2.1,
has a unique efficient dominating set D. Specifically,
.
2) The path
has a unique efficient dominating set
and any path
such that
can be constructed from copies of
by identifying the vertices on the ends. By Theorem 2.3,
has a unique efficient dominating set D. Specifically,
.
3) By Lemma 1.2 iv), either
or
is in the efficient dominating set of G. By Lemma 1.3,
is an efficient dominating set of G if
, and
is an efficient dominating set of G if
. Thus, G has two efficient dominating sets.
Theorem 3.2. A path
has a unique efficient dominating set if and only if
.
The following corollary follows from Theorem 2.3 and Lemma 3.1 2). It can be considered a generalization of Theorem 2.2.
Corollary 3.3. Let
and
be two graphs with unique efficient dominating sets
and
, respectively. Let
and
. If G is the graph obtained from
, where
, by identifying
with one end vertex of
and
with the other end vertex of
, then
is the unique efficient dominating set of G.
Interestingly, trees can be formed by connecting and identifying vertices of paths. If a tree can be generated by combining paths with unique efficient dominating sets using the operations described in Section 2, the tree itself will also have a unique efficient dominating set.
The logical step after considering paths is to have a result for cycles. The following result follows from the previous theorem on paths.
Theorem 3.4. A cycle
has an efficient dominating set if and only if
. Furthermore,
has 3 efficient dominating sets.
Proof. Let
and let D be an efficient dominating set of
. Since each vertex in D dominates two other vertices, the total number of vertices is a multiple of 3. Hence,
. By Lemma 1.3,
,
, and
are three efficient dominating sets of
.
When we combine a path and a cycle, we can form a tadpole graph. The
-tadpole graph, also called a dragon graph, is the graph obtained from a cycle
and a path
by connecting
and
.
Lemma 3.5. Let G be an
-tadpole graph, where
,
, and
.
1) If
, then G has 3 efficient dominating sets.
2) If
, then G has a unique efficient dominating set.
3) If
, then G has 2 efficient dominating sets.
Proof. Consider
and its three neighbors
,
and
. Exactly one of these 4 vertices is in D. If
is in D, then by Lemma 1.3,
must be in D, and similarly
are all in D. But
is dominated by two vertices
and
, a contradiction. Therefore
.
1) Suppose that
. By Lemma 1.3,
is an efficient dominating set of G if
,
is an efficient dominating set of G if
, and
is an efficient dominating set of G if
. Therefore, G has 3 efficient dominating sets.
2) Suppose that
. If
or
, then by Lemma 1.3,
must be in D. In that case,
cannot be efficiently dominated, a contradiction. So
and
, which means
. By Lemma 1.3,
is an efficient dominating set of G. Therefore, G has a unique efficient dominating set.
3) Suppose that
. If
, then by Lemma 1.3,
are all in D. In that case,
cannot be efficiently dominated, a contradiction. So
, which means
or
. By Lemma 1.3,
is an efficient dominating set of G if
, and
is an efficient dominating set of G if
. Therefore G has two efficient dominating sets.
Lemma 3.6. Let G be an
-tadpole graph, where
and
.
1) If
, then G does not have an efficient dominating set.
2) If
, then G has a unique efficient dominating set if and only if
.
Proof. Consider
and its three neighbors
,
and
. Exactly one of these 4 vertices is in D.
1) Suppose that
. If
, then by Lemma 1.3,
. In that case,
is dominated by two vertices, a contradiction. If
, then by Lemma 1.3,
. In that case,
is dominated by two vertices, a contradiction. By argument similar to
,
. If
, then by Lemma 1.3,
. In that case,
cannot be efficiently dominated, a contradiction. Thus, G does not have an efficient dominating set.
2) Suppose that
. If
, then by Lemma 1.3,
. Now
and
are both in D, a contradiction. If
, then by Lemma 1.3,
and then
cannot be efficiently dominated, a contradiction. By argument similar to
,
. If
, then by Lemma 1.3,
and
. So only when
, G has a unique efficient dominating set.
The following complete characterization of tadpole graphs with unique efficient dominating sets follows from Lemma 3.5 and Lemma 3.6.
Theorem 3.7. Let G be an
-tadpole graph, where
and
. Then G has a unique efficient dominating set if and only if
and
, or
and
.
Since Lemma 1.3 is used extensively, it will not be stated in the following proofs for the sake of brevity.
3.2. Sunlet/Centipede/Firecracker/Caterpillar Graphs
In this section, the authors prove that sunlet graphs, centipede graphs, and firecracker graphs all have unique efficient dominating sets. Furthermore, the authors characterize all the caterpillar graphs which have unique efficient dominating sets.
A k-star is a graph isomorphic to
with
, where
is the center. The n-sunlet graph is the graph on 2n vertices obtained from a cycle
by attaching n pendant edges
,
[3]. The n-centipede graph is the graph on 2n vertices obtained from a path
by attaching
pendant edges
,
[3]. An
-firecracker is a graph obtained from n copies of k-stars by connecting
, where
is a leaf from the i-th star and
.
Theorem 3.8. If G is one of the following graphs, then G has a unique efficient dominating set of order n.
1) G is an n-sunlet graph.
2) G is an n-centipede graph with
.
3) G is an
-firecracker with
.
Proof. 1) By Lemma 1.2 vi), the set of all the pendant vertices of an
-sunlet graph is the unique efficient dominating set of G.
2) By Lemma 1.2 vi), the set of all the pendant vertices of an
-centipede graph is the unique efficient dominating set of G.
3) By Lemma 1.2 v), the center of each star is its unique efficient dominating set. Since G can be constructed from stars by the operation described in Theorem 2.1, G has a unique efficient dominating set, which is the set of all the centers of all the stars.
A caterpillar graph is a tree in which every vertex is on a central stalk or only one edge away from the stalk. In other words, removal of its endpoints leaves a path (central stalk). A tree is a caterpillar if and only if all vertices of degree at least 3 are surrounded by at most two vertices of degree two or greater.
We will call a vertex
on the main stalk a star vertex or s-vertex if
, and we will call a vertex
on the main stalk a p-vertex if
( p refers to the single pendant vertex of
). Furthermore, we call a vertex
on the main stalk a trivial vertex if
, and a nontrivial vertex if
. A pair of nontrivial vertices
is called a pair-
if there are no p-vertices or s-vertices between them and on the main stalk there are n mod 3 vertices between them.
To characterize the caterpillar graphs G which have unique efficient dominating sets, we can make the following assumptions.
a) G has at least two nontrivial vertices.
If G doesn’t have nontrivial vertices, then G is a path. If G has exactly one nontrivial vertex, then G is a spider graph. Both are discussed in this paper, respectively.
b) Every pendant vertex is adjacent to a nontrivial vertex.
If there are pendant vertices adjacent to a trivial vertex (vertex of degree 2) in a caterpillar graph, then there are at most two such vertices on the ends. The caterpillar graph can be decomposed into a caterpillar graph without such vertices and two paths.
c) There is no induced path of length 5 with internal vertices of degree 2 in G.
This assumption is based on Theorem 2.6. So for any pair-
, there are at most two vertices of degree 2 between them. This implies that for a pair-
, there are exactly
trivial vertices (vertices of degree 2) between them.
Lemma 3.9. Let G be a caterpillar graph with a unique efficient dominating set D. Let
and
be pendant vertices connected to
and
, respectively.
1) If
and
are a pair-2, then
.
2) If
and
are a pair-0, then
.
3) If
and
are a pair-1, then
and
is a p-vertex, or
and
is a p-vertex.
Proof. 1) Suppose that
are the two vertices of degree 2 between
and
such that
. By Lemma 1.2 iv),
and
. In order to dominate
and
, we have
.
2) By Lemma 1.2 iv),
and
. In order to dominate
and
, it is the case that
. 3) Suppose that
. By Lemma 1.2 i),
. By Lemma 1.2 iv),
and by Lemma 1.2 v),
is a p-vertex. Similarly, we can prove that if
, then
and
is a p-vertex.
For the caterpillar graph G, if there are more than one p-vertices
such that
for
, we will call
a cluster of pair-0.
Lemma 3.10. Let G be a caterpillar graph and
be a pair-2 of G. Suppose that
is the graph obtained from G by contracting the path of length 3 between
and
to a single vertex w. Then G has a unique efficient dominating set D if and only if
has a unique efficient dominating set
.
Proof. If G has a unique efficient dominating set D, then by Lemma 3.9 1),
, and
is an efficient dominating set of
. If
has a unique efficient dominating set
, then by Lemma 1.2 v),
, and
is an efficient dominating set of G. Notice that there is a one-to-one correspondence between the efficient dominating sets of G and the efficient dominating sets of
. Therefore, G has a unique efficient dominating set D if and only if
has a unique efficient dominating set
.
Based on Lemma 3.10, we can further assume that d) the caterpillar graphs under consideration don’t have pair-2.
Theorem 3.11. Let G be a caterpillar graph satisfying a)-d). Then G has a unique efficient dominating set D if and only if the following four conditions are true.
1) If G has more than one s-vertex, then for any two neighboring s-vertices
and
(no other s-vertices in between), then there are an even number of trivial vertices (vertices of degree 2) between them.
2) If G doesn’t have s-vertices, then G must have a pair-0.
3) Between any two neighboring clusters of pair-0 (no other cluster of pair-0 in between), there are even number of trivial vertices (vertices of degree 2).
4) Between an s-vertex and a cluster of pair-0, there are odd number of trivial vertices (vertices of degree 2).
Proof. Suppose that G is a caterpillar graph satisfying a)-d), and that G has a unique dominating set D.
Suppose that G has more than one s-vertices and let
and
be two neighboring s-vertices (no other s-vertices in between). By Lemma 1.2 v),
and
are both in D. Based on the assumption d), there are only pair-1 and pair-0 between
and
. Then there must be an even number of pair-1 between
and
. This is because when there is a sequence of consecutive pair-1, by Lemma 3.9 3) the vertex that is in D will alternate between being on the main stalk and being the pendant vertex. In order to ensure that the first vertex
and the last vertex
are both in D, there most be an even number of pair-1. So 1) is true.
Suppose that G does not have s-vertices. Suppose that G doesn’t have a pair-0. Then all the nontrivial vertices of G are p-vertices, and G doesn’t have pair-0 or pair-2. So by Lemma 3.9 3), G has two efficient dominating sets, a contradiction. So G must have a pair-0 and then 2) is true.
Suppose that
and
are two neighboring nontrivial vertices (no other nontrivial vertices in between) of G such that
is a vertex in a cluster of pair-0 and
is a vertex in another cluster of pair-0. By Lemma 3.9 2),
and
, where
is the pendant vertex adjacent to
and
is the pendant vertex adjacent to
. There must be even number of trivial vertices (vertices of degree 2) between
and
. So 3) is true.
Suppose that
and
are two neighboring nontrivial vertices (no other nontrivial vertices in between) of G such that
is an s-vertex and
is a vertex in a cluster of pair-0. Since
and
, where
is the pendant vertex adjacent to
, there must be odd number of trivial vertices (vertices of degree 2) between
and
. So 4) is true.
Conversely, suppose that G is a caterpillar graph satisfying a)-d) and 1)-4).
If G has s-vertices, then by Lemma 1.2 v), all the s-vertices are in D. Since G satisfies 1), 3) and 4), all the vertices between s-vertices, between clusters of pair-0, or between s-vertices and clusters of pair-0, are either in D or efficiently dominated.
Assume that G has exactly one s-vertex
and G has no cluster of pair-0. So all the nontrivial vertices of G except
are all p-vertices and G has pair-1 only. By Lemma 1.2 v),
. By Lemma 3.9 3), the efficient dominating set of G is uniquely determined based on the fact that
.
Similarly if G has exactly one cluster of pair-0, then all the nontrivial vertices of G are all p-vertices and G has pair-1 (except the cluster of pair-0) only. Then the efficient dominating set of G is uniquely determined.
3.3. Spider Graphs
The following results provide a comprehensive summary of efficient dominating sets of spider graphs, which is a specific type of tree.
For
, let
and let
be the graph generated from
by identifying
as a single vertex
. Then
is called a spider graph with center
and
legs, where
denotes the length and the number of vertices on the ith leg. If
, then S is just a path. Thus, the following theorems assume that S has at least 3 legs, that is,
.
Lemma 3.12. Let G denote the spider graph
with center
and
legs, where
denotes the length of the ith leg. If G has a unique efficient dominating set D, then the following statements are true.
1) If
, then
.
2) If
, then
.
3) If
, then
for any
.
Proof. 1) Suppose that
. If
, then
. In this case,
is not dominated by any vertex in D, a contradiction.
2) Suppose that
. If
, then
. In this case,
is not dominated by any vertex in D, a contradiction.
3) Suppose that
. If
, then
. In this case,
is not dominated by any vertex in D, a contradiction.
Lemma 3.13. Let G denote the spider graph
with center
and n legs, where
denotes the length of the
th leg.
1) If
for
, then G has a unique efficient dominating set.
2) If
for
, then G has a unique efficient dominating set.
3) If
for
, then G has n efficient dominating sets.
Proof. 1) By definition, G is generated from
by identifying
as a single vertex
. Since
are all equal to 0 mod 3, it is the case that
are all paths with number of vertices equal to 1 (mod 3). By Theorem 3.1 2), for each
,
has a unique efficient dominating set
. By Theorem 2.3, G has a unique efficient dominating set
, where we consider
.
2) Consider the star graph
with center
. The center
has
neighbors
. By Lemma 1.2 v),
is the efficient dominating set. For
, define
. Then,
vertices. By Lemma 3.1 1),
has a unique efficient dominating set
. Since G can be constructed from the star graph
and
, where
, by connecting
to
, by Theorem 2.1, G has a unique dominating set
.
3) Let D be an efficient dominating set of G. If
, then for
,
and then
is not dominated by any vertex in D, a contradiction. Therefore,
. Since
, one of
must be in D. If
, then
. Thus, G has n efficient dominating sets.
In the following proof, a Type-n leg is defined to be a leg with
mod 3 vertices, not counting the vertex that becomes the center.
Theorem 3.14. Let G denote the spider graph
with center
and
legs, where
denotes the length of the
th leg. Then G has a unique efficient dominating set if and only if one of the following holds.
1) G has Type-0 legs only.
2) G has Type-1 legs only.
3) G doesn’t have Type-1 legs, and G has exactly one Type-2 leg.
4) G has exactly one Type-1 leg, and G has a Type-2 leg.
5) G has more than one Type-1 leg, and G doesn’t have Type-2 legs.
Proof. Suppose that G has a unique efficient dominating set. We distinguish the following three cases.
Case 1: G doesn’t have Type-1 legs.
If G doesn’t have Type-2 legs, then G satisfies 1). If G has exactly one Type-2 leg, then G satisfies 3). Suppose that G has more than one Type-2 leg, and let
and
be two Type-2 legs. By Lemma 3.12 1),
. Let
be the leg of G such that
dominates
. By Lemma 3.12 2),
is not a Type-0 leg and so
must be a Type-2 leg. If
is a Type-2 leg with
, then
; if
is a Type-0 leg, then
; for the Type-2 leg
,
. In that case, G has more than one efficient dominating set, a contradiction.
Case 2: G has exactly one Type-1 leg.
Suppose that G does not have Type-2 legs. Then G has one Type-1 leg and more than one Type-0 legs. If
, then
if
is a Type-0 leg and
if
is a Type-1 leg. If
, then
if
is a Type-0 leg and
if
is a Type-1 leg. Now G has two efficient dominating sets, a contradiction. So G must have Type-2 legs and then G satisfies 4).
Case 3: G has more than one Type-1 leg.
Let
and
be two Type-1 legs. By Lemma 3.12 3),
. Suppose that G has a Type-2 leg
. Then by Lemma 1.3,
. In this case,
cannot be efficiently dominated. So G doesn’t have Type-2 legs. Therefore, G satisfies 2) or 5).
Conversely, if G satisfies 1) or 2), then by Lemma 3.13, G has a unique efficient dominating set. Suppose that D is an efficient dominating set of G. We prove that G has a unique efficient dominating set asuming G satisfies condition 3), 4) or 5), respectively.
3) G doesn’t have Type-1 legs, and G has exactly one Type-2 leg.
Since G has a Type-2 leg, by Lemma 3.12 1),
. Then there is
. By Lemma 3.12 2),
is not a Type-0 leg. Since G doesn’t have Type-1 legs,
must be the Type-2 leg. So for any Type-0 leg
,
, and for the Type-2 leg
,
. Thus, G has a unique efficient dominating set.
4) G has exactly one Type-1 leg, and G has a Type-2 leg.
Since G has a Type-2 leg, by Lemma 3.12 1),
. Then there is
. By Lemma 3.12 2),
is not a Type-0 leg and by Lemma 3.12 3),
is not a Type-2 leg. So
must be the Type-1 leg. So for any Type-0 leg
,
, for the Type-1 leg
,
, and for any Type-2 leg
,
. Thus, G has a unique efficient dominating set.
5) G has more than one Type-1 leg, and G doesn’t have a Type-2 leg.
Since G has more than one Type-1 leg, by Lemma 3.12 3),
for any
. So
and for any Type-0 leg
,
, and for the Type-1 leg
,
. Thus, G has a unique efficient dominating set.
3.4. Further Discussion
Theorem 3.15. Let G be a graph with independent set
such that 1)
and 2) for every vertex in
and
,
. Then
is the unique efficient dominating set of G.
Proof. Based on the fact that D is an independent set and every vertex in
is dominated by exactly one vertex from D, D is an efficient dominating set. We just need to prove that D is the only efficient dominating set of G.
Suppose that
is an efficient dominating set. Suppose that
. Then there must be a vertex
such that
. Since
is independent, no vertex of
can be an element of
. Since
,
is not in
(Otherwise, every vertex in
is dominated by
and
). Now
is not dominated by any vertex of
. Therefore
. Similarly,
for any
. So
. By Theorem 1.1,
. So D is the unique efficient dominating set of G.
Corollary 3.16. Let G be a graph obtained from
by adding
and connecting
to each vertex in
for
. Then
is the unique efficient dominating set of G.
Corollary 3.17. Let G be a graph obtained from
by adding
and connecting
to each vertex in
for
, where
. Then
is the unique efficient dominating set of G.