Unique Efficient Dominating Sets

Isaac Reiter, Ju Zhou

Department of Mathematics, Kutztown University of Pennsylvania, Kutztown, PA, USA.

DOI: 10.4236/ojdm.2020.102006                

Abstract

Given a finite simple graph G, a set D ⊆ V(G) is called a dominating set if for all v ∈ V(G) , either v ∈ D or v is adjacent to some vertex in D. A dominating set D is independent if none of the vertices in D are adjacent, and D is 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. 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. In this paper, the authors propose the definition of unique efficient dominating set, explore the properties of graphs with unique efficient dominating sets, and completely characterize several families of graphs which have unique efficient dominating sets.

Keywords

Dominating Set, Minimum Dominating Set, Efficient Dominating Set, Unique Efficient Dominating Set

1. Introduction

Let G be a simple finite graph and $u\mathrm{,}v$ be two vertices of G. We use $d\left(u\mathrm{,}v\right)$ to denote the distance, or the shortest length of paths between $u$ and $v$, $N\left(u\right)$ to denote the set of vertices adjacent to $u$ and $N\left[u\right]=N\left(u\right)\cup \left\{u\right\}$. Furthermore, we use $d_G\left(u\right)$ or $d\left(u\right)$ to denote the cardinality of $N\left(u\right)$.

Given a finite simple graph G, a set $D\subseteq V\left(G\right)$ is called a dominating set if for all $v\in V\left(G\right)$, either $v\in D$ or $v$ 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 $u\mathrm{,}v\in D$, $d\left(u\mathrm{,}v\right)\ge 3$.

ii) For any vertex $u\in D$, there exists a vertex $v\in D$ such that $d\left(u\mathrm{,}v\right)=3$.

iii) $V\left(G\right)$ is the disjoint union of all $N\left[u\right]$, where $N\left[u\right]=N\left(u\right)\cup \left\{u\right\}$ and $u\in D$.

iv) If $uv\in E\left(G\right)$ and $d\left(v\right)=1$, then either $u\in D$ or $v\in D$. Furthermore, if $w\in N\left(u\right)\backslash \left\{v\right\}$, then $w\cancel{\in }D$.

v) If $v_1\mathrm{,}{v}_2\in N\mathrm{<mo\; stretchy="false">\; (\; </mo>}u\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and $d\left(v_1\right)=d\left(v_2\right)=1$, then $u\in D$.

vi) If $d\left(u\mathrm{,}v\right)=3$ and $d\left(u\right)=d\left(v\right)=1$, then $u\mathrm{,}v\in D$.

Proof. i) It follows directly from the fact that an efficient dominating set is independent and perfect.

ii) Let $V_1\mathrm{<mo>\; =\; </mo>}N\mathrm{<mo\; stretchy="false">\; (\; </mo>}u\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and $V_2=N\left(V_1\right)\backslash \left(V_1\cup \left\{u\right\}\right)$. Since D is independent and perfect, $V_1\cap D=\varnothing$ and $V_2\cap D=\varnothing$. This implies that the vertices in $V_2$ are dominated by one or more vertices other than $u$. Let $v$ be one of these vertices. Then it follows that $d\left(u\mathrm{,}v\right)=3$.

iii) For any $v\in V\left(G\right)$, if $v\cancel{\in }D$, there is a unique vertex $u\in D$ such that $v$ is dominated by $u$. That is to say, there is a unique vertex $u\in D$ such that $v\in N\left(u\right)$. Therefore, $V\left(G\right)$ is the disjoint union of $N\left[u\right]$ for all the $u\in D$ and so iii) follows.

iv) Since D is an efficient dominating set of G and $d\left(v\right)=1$, it follows that either $u\in D$ or $v\in D$. If $w\in N\left(u\right)\backslash \left\{v\right\}$, then $d\left(u\mathrm{,}w\right)=1$ and $d\left(u\mathrm{,}w\right)=2$. By i), $w\cancel{\in }D$.

v) Suppose that $v_1\in D$. Since $u{v}_1\in E\left(G\right)$ and $d\left(v_1\mathrm{,}{v}_2\right)=2$, $u\cancel{\in }D$ and $v_2\cancel{\in }D$, which contradicts iv). Therefore, $v_1\cancel{\in }D$ and by iv), $u\in D$.

vi) Let $u{u}_1{v}_{1}v$ be a path of G. If $u\cancel{\in }D$, then $u_1\in D$. By i), $v_1\cancel{\in }D$ and $v\cancel{\in }D$. So $v$ is not dominated by any vertex in D, a contradiction. Therefore, $u\in D$ and similarly $v\in D$.

Lemma 1.3. Suppose that $H=G\left[\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$ is a path with $d_G\left(v_2\right)=d_G\left(v_3\right)=2$. Let D be an efficient dominating set of G. If $v_1\in D$, then $v_4\in D$.

Proof. By Lemma 1.2 i), $v_2\cancel{\in }D$ and $v_3\cancel{\in }D$. By the fact that H is a path with $d_G\left(v_2\right)=d_G\left(v_3\right)=2$, $v_4\in D$. Otherwise, $v_3$ 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 $G_1$ and $G_2$ be two graphs with unique efficient dominating sets $D_1$ and $D_2$, respectively. Let $u_1$ and $u_2$ be two vertices in $V\left(G_1\right)-D_1$ and $V\left(G_2\right)-D_2$, respectively. If G is the graph obtained from $G_1\cup G_2$ by connecting $u_1$ and $u_2$ with an edge, that is, $G=G_1\cup G_2\cup \left\{u_1{u}_2\right\}$, then $D_1\cup D_2$ is the unique efficient dominating set of G.

Proof. Since for $i=1,2$, $D_i$ is the unique efficient dominating set of $G_i$, $D_1\cup D_2$ is an efficient dominating set of G. Suppose that there exists an efficient dominating set $D^{\prime }$ of G. Suppose that $u_1\in D^{\prime }$. Then ${D^{\prime }}_1=D^{\prime }\cap V\left(G_1\right)$ is an efficient dominating set of $G_1$. Since $u_1\in {D^{\prime }}_1$ and $u_1\cancel{\in }{D}_1$, ${D^{\prime }}_1\ne D_1$, contradicting the fact that $G_1$ has a unique efficient dominating set. Therefore, $u_1\notin D^{\prime }$ and similarly $u_2\notin D^{\prime }$. Thus, for $i=1,2$, $u_i$ is dominated by a vertex of $G_i$ and so ${D^{\prime }}_i=D^{\prime }\cap V\left(G_i\right)$ is an efficient dominating set of $G_i$. Since $D_i$ is the unique efficient dominating set of $G_i$, ${D^{\prime }}_i=D_i$. So $D^{\prime }={D^{\prime }}_1\cup {D^{\prime }}_2=D_1\cup D_2$. Hence, $D_1\cup D_2$ is the unique efficient dominating set of G.

Theorem 2.2. Let $G_1$ and $G_2$ be two graphs with unique efficient dominating sets $D_1$ and $D_2$, respectively. Let $v_1\in D_1$ and $v_2\in D_2$. If G is the graph obtained from $G_1\cup G_2$ by adding two new vertices $u_1$ and $u_2$, and three edges $u_1{u}_2$, $u_1{v}_1$ and $u_2{v}_2$, then $D_1\cup D_2$ is the unique efficient dominating set of G.

Proof. Since for $i=1,2$, $D_i$ is the unique efficient dominating set of $G_i$, $D_1\cup D_2$ is an efficient dominating set of G. Suppose that G has another efficient dominating set $D^{\prime }$. Suppose that $u_1\in D^{\prime }$. Since $u_2$ is dominated by $u_1$, $v_2\notin D^{\prime }$. Then ${D^{\prime }}_2=D^{\prime }\cap V\left(G_2\right)$ is an efficient dominating set of $G_2$ with $v_2\cancel{\in }{D^{\prime }}_2$. Since $v_2\in D_2$, ${D^{\prime }}_2\ne D_2$, contradicting the fact that $D_2$ is a unique efficient dominating set of $G_2$. Hence, $u_1\notin D^{\prime }$ and similarly $u_2\notin D^{\prime }$. In order to ensure that $u_1$ and $u_2$ are dominated, it is the case that $v_1\in D^{\prime }$ and $v_2\in D^{\prime }$. So for $i=1,2$, ${D^{\prime }}_i=D^{\prime }\cap V\left(G_i\right)$ is an efficient dominating set of $G_i$. Since $D_i$ is the unique efficient dominating set of $G_i$, ${D^{\prime }}_i=D_i$ and so $D^{\prime }={D^{\prime }}_1\cup {D^{\prime }}_2=D_1\cup D_2$. Hence, $D_1\cup D_2$ 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 $G_1$ and $G_2$ be two graphs with unique efficient dominating sets $D_1$ and $D_2$, respectively. Let $v_1\in D_1$ and $v_2\in D_2$. If G is the graph obtained from $G_1\cup G_2$ by identifying $v_1$ and $v_2$ as a single vertex $v$, then $D_1\cup D_2$ is the unique efficient dominating set of G.

Proof. Since for $i=1,2$, $D_i$ is the unique efficient dominating set of $G_i$, $D_1\cup D_2$ is an efficient dominating set of G. Let $D^{\prime }$ be another efficient dominating set of G. Suppose that $v\notin D^{\prime }$, and without loss of generality, suppose that $v$ is dominated by a vertex in $V\left(G_1\right)\cap D^{\prime }$. Then ${D^{\prime }}_1=D^{\prime }\cap V\left(G_1\right)$ is an efficient dominating set of $G_1$. Since $v_1=v\cancel{\in }{D^{\prime }}_1$ and $v_1\in D_1$, ${D^{\prime }}_1\ne D_1$, contradicting the fact that $G_1$ has a unique efficient dominating set. Thus, $v\in D^{\prime }$, and ${D^{\prime }}_i=D^{\prime }\cap V\left(G_i\right)$ is an efficient dominating set of $G_i$. Since $D_i$ is the unique efficient dominating set of $G_i$, ${D^{\prime }}_i=D_i$ and so $D^{\prime }={D^{\prime }}_1\cup {D^{\prime }}_2=D_1\cup D_2$. Hence, $D_1\cup D_2$ 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 $G_1$ and $G_2$ be two graphs with unique efficient dominating sets $D_1$ and $D_2$, respectively. Let $v_1\in V\left(G_1\right)$ and $v_2\in V\left(G_2\right)$ be two pendant vertices such that $v_1\in D_1$ and $v_2\in D_2$. Denote the neighbors of $v_1$ and $v_2$ as $u_1$ and $u_2$, respectively. If G is the graph obtained from $G_1\cup G_2$ by identifying $v_1$ and $v_2$ as a single vertex $v$ and by identifying $u_1$ and $u_2$ as a single vertex $u$, then G has the unique efficient dominating set $D_1\cup D_2$.

Proof. Since for $i=1,2$, $D_i$ is the unique efficient dominating set of $G_i$, $D_1\cup D_2$ is an efficient dominating set of G. Suppose that G has another efficient dominating set $D^{\prime }$. Since $uv\in E\left(G\right)$ and $d\left(v\right)=1$, by Lemma 1.2 iv), $u\in D^{\prime }$ or $v\in D^{\prime }$. Suppose that $u\in D^{\prime }$. Then for $i=1,2$, ${D^{\prime }}_i=D^{\prime }\cap V\left(G_i\right)$ is an efficient dominating set of $G_i$. Since $u_i=u\in {D^{\prime }}_i$ but $u_i\cancel{\in }{D}_i$, ${D^{\prime }}_i\ne D_i$, contradicting the fact that $G_i$ has a unique efficient dominating set. So $u\cancel{\in }{D}^{\prime }$ and then $v\in D^{\prime }$. Now ${D^{\prime }}_i=D^{\prime }\cap V\left(G_i\right)$ is an efficient dominating set of $G_i$. Since $D_i$ is the unique efficient dominating set of $G_i$, ${D^{\prime }}_i=D_i$ and so $D^{\prime }={D^{\prime }}_1\cup {D^{\prime }}_2=D_1\cup D_2$. Hence, $D_1\cup D_2$ is the unique efficient dominating set of G.

Theorem 2.5. Let $G_1$ and $G_2$ be two graphs with unique efficient dominating sets $D_1$ and $D_2$, respectively. Let $v_1\in V\left(G_1\right)$ and $v_2\in V\left(G_2\right)$ be two pendant vertices with neighbors $u_1$ and $u_2$ such that $u_1\in D_1$ and $u_2\in D_2$. If G is the graph obtained by identifying $v_1$ and $v_2$ as a single vertex $v$ and by identifying $u_1$ and $u_2$ as a single vertex $u$, then G has the unique efficient dominating set $D_1\cup D_2$.

Proof. Since for $i=1,2$, $D_i$ is the unique efficient dominating set of $G_i$, $D_1\cup D_2$ is an efficient dominating set of G. Suppose that G has another efficient dominating set $D^{\prime }$. Since $uv\in E\left(G\right)$ and $d\left(v\right)=1$, by Lemma 1.2 iv), $u\in D^{\prime }$ or $v\in D^{\prime }$. Suppose that $v\in D^{\prime }$. Then for $i=1,2$, ${D^{\prime }}_i=D^{\prime }\cap V\left(G_i\right)$ is an efficient dominating set of $G_i$. Since $v_i=v\in {D^{\prime }}_i$ but $v_i\cancel{\in }{D}_i$, ${D^{\prime }}_i\ne D_i$, contradicting the fact that $G_i$ has a unique efficient dominating set. So $v\cancel{\in }{D}^{\prime }$ and then $u\in D^{\prime }$. Now ${D^{\prime }}_i=D^{\prime }\cap V\left(G_i\right)$ is an efficient dominating set of $G_i$. Since $D_i$ is the unique efficient dominating set of $G_i$, ${D^{\prime }}_i=D_i$ and so $D^{\prime }={D^{\prime }}_1\cup {D^{\prime }}_2=D_1\cup D_2$. Hence, $D_1\cup D_2$ is the unique efficient dominating set of G.

Theorem 2.6. Suppose that $H=G\left[\left\{v_0\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$ is a path with $d_G\left(v_1\right)=d_G\left(v_2\right)=d_G\left(v_3\right)=2$. Let $G^{\prime }$ be a graph obtained from G by deleting $v_1\mathrm{,}{v}_2\mathrm{,}{v}_3$ and connecting $v_0$ and $v_4$. Then G has a unique efficient dominating set if and only if $G^{\prime }$ has a unique efficient dominating set.

Proof. Suppose that D is an efficient dominating set of G. If $v_2\in D$, then by Lemma 1.2 i), $v_0\cancel{\in }D$ and $v_4\cancel{\in }D$. In this case, $D-\left\{v_2\right\}$ is an efficient dominating set of $G^{\prime }$. If $v_2\cancel{\in }D$, then either $v_1\in D$ or $v_3\in D$. Without loss of generality, suppose that $v_1\in D$. By Lemma 1.3, $v_4\in D$. Since $v_0\cancel{\in }D$ and $\left(N\left(v_0\right)\backslash \left\{v_1\right\}\right)\cap D=\varnothing$ (since $v_1\in D$ ), $D-\left\{v_1\right\}$ is an efficient dominating set of $G^{\prime }$ with $v_4$ dominating $v_0$.

Suppose that $D^{\prime }$ is an efficient dominating set of $G^{\prime }$. If $v_0\cancel{\in }{D}^{\prime }$ and $v_4\cancel{\in }{D}^{\prime }$, then $D^{\prime }\cup \left\{v_2\right\}$ is an efficient dominating set of G. If $v_0\in D$ or $v_4\in D$, say $v_0\in D$, then $D^{\prime }\cup \left\{v_3\right\}$ 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 $G^{\prime }$. Therefore, G has a unique efficient dominating set if and only if $G^{\prime }$ 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 $P_n=v_1{v}_2{v}_3\cdots v_n$.

Lemma 3.1. If $G\cong P_n$, then the following conclusions are true.

1) If $n=0\left(\mathrm{mod}3\right)$, then G has a unique efficient dominating set.

2) If $n=1\left(\mathrm{mod}3\right)$, then G has a unique efficient dominating set.

3) If $n=2\left(\mathrm{mod}3\right)$, then G has two efficient dominating sets.

Proof. Suppose that D is an efficient dominating set of G.

1) The path $P_3$ has a unique efficient dominating set $\left\{v_2\right\}$, and any path $P_n$ such that $n=0\left(\mathrm{mod}3\right)$ can be constructed from copies of $P_3$ by connecting the vertices on the ends. By Theorem 2.1, $P_n$ has a unique efficient dominating set D. Specifically, $D=\left\{v_2\mathrm{,}{v}_5\mathrm{,}{v}_8\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\right\}$.

2) The path $P_4$ has a unique efficient dominating set $\left\{v_1\mathrm{,}{v}_4\right\}$ and any path $P_n$ such that $n=1\left(\mathrm{mod}3\right)$ can be constructed from copies of $P_4$ by identifying the vertices on the ends. By Theorem 2.3, $P_n$ has a unique efficient dominating set D. Specifically, $D=\left\{v_1\mathrm{,}{v}_4\mathrm{,}{v}_7\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$.

3) By Lemma 1.2 iv), either $v_1$ or $v_2$ is in the efficient dominating set of G. By Lemma 1.3, $D=\left\{v_1\mathrm{,}{v}_4\mathrm{,}{v}_7\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\right\}$ is an efficient dominating set of G if $v_1\in D$, and $D=\left\{v_2\mathrm{,}{v}_5\mathrm{,}{v}_8\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ is an efficient dominating set of G if $v_2\in D$. Thus, G has two efficient dominating sets.

Theorem 3.2. A path $P_n$ has a unique efficient dominating set if and only if $n\ne 2\left(\mathrm{mod}3\right)$.

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 $G_1$ and $G_2$ be two graphs with unique efficient dominating sets $D_1$ and $D_2$, respectively. Let $v_1\in D_1$ and $v_2\in D_2$. If G is the graph obtained from $G_1\cup G_2\cup P_n$, where $n=1\left(\mathrm{mod}3\right)$, by identifying $v_1$ with one end vertex of $P_n$ and $v_2$ with the other end vertex of $P_n$, then $D_1\cup D_2\cup \left\{v_4\mathrm{,}{v}_7\mathrm{,}\cdots \mathrm{,}{v}_{n-3}\right\}$ 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 $C_n$ has an efficient dominating set if and only if $n=0\left(\mathrm{mod}3\right)$. Furthermore, $C_n$ has 3 efficient dominating sets.

Proof. Let $C_n=v_1{v}_2{v}_3\cdots v_n{v}_1$ and let D be an efficient dominating set of $C_n$. Since each vertex in D dominates two other vertices, the total number of vertices is a multiple of 3. Hence, $n=0\left(\mathrm{mod}3\right)$. By Lemma 1.3, $D_1=\left\{v_1\mathrm{,}{v}_4\mathrm{,}{v}_7\mathrm{,}\cdots \mathrm{,}{v}_{n-2}\right\}$, $D_2=\left\{v_2\mathrm{,}{v}_5\mathrm{,}{v}_8\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\right\}$, and $D_3=\left\{v_3\mathrm{,}{v}_6\mathrm{,}{v}_9\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ are three efficient dominating sets of $C_n$.

When we combine a path and a cycle, we can form a tadpole graph. The $\left(m\mathrm{,}n\right)$ -tadpole graph, also called a dragon graph, is the graph obtained from a cycle $C_m=u_1{u}_2\cdots u_m{u}_1$ and a path $P_n=v_1{v}_2\cdots \mathrm{,}{v}_n$ by connecting $u_1$ and $v_1$.

Lemma 3.5. Let G be an $\left(m\mathrm{,}n\right)$ -tadpole graph, where $m\ge 3$, $n=0\left(\mathrm{mod}3\right)$, and $n\ge 1$.

1) If $n=0\left(\mathrm{mod}3\right)$, then G has 3 efficient dominating sets.

2) If $n=1\left(\mathrm{mod}3\right)$, then G has a unique efficient dominating set.

3) If $n=2\left(\mathrm{mod}3\right)$, then G has 2 efficient dominating sets.

Proof. Consider $u_1$ and its three neighbors $u_2$, $u_m$ and $v_1$. Exactly one of these 4 vertices is in D. If $v_1$ is in D, then by Lemma 1.3, $u_3$ must be in D, and similarly $u_6\mathrm{,}{u}_9\mathrm{,}\cdots \mathrm{,}{u}_m$ are all in D. But $u_1$ is dominated by two vertices $u_m$ and $v_1$, a contradiction. Therefore $v_1\cancel{\in }D$.

1) Suppose that $n=0\left(\mathrm{mod}3\right)$. By Lemma 1.3, $D=\left\{u_1\mathrm{,}{u}_4\mathrm{,}{u}_7\mathrm{,}\cdots \mathrm{,}{u}_{m-2}\mathrm{,}{v}_3\mathrm{,}{v}_6\mathrm{,}{v}_9\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ is an efficient dominating set of G if $u_1\in D$, $D=\left\{u_2\mathrm{,}{u}_5\mathrm{,}{u}_8\mathrm{,}\cdots ,u_{m-1}\mathrm{,}{v}_2\mathrm{,}{v}_5\mathrm{,}{v}_8\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\right\}$ is an efficient dominating set of G if $u_2\in D$, and $D=\left\{u_3\mathrm{,}{u}_6\mathrm{,}{u}_9\mathrm{,}\cdots ,u_m\mathrm{,}{v}_2\mathrm{,}{v}_5\mathrm{,}{v}_8\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\right\}$ is an efficient dominating set of G if $u_m\in D$. Therefore, G has 3 efficient dominating sets.

2) Suppose that $n=1\left(\mathrm{mod}3\right)$. If $u_2\in D$ or $u_m\in D$, then by Lemma 1.3, $v_2\mathrm{,}{v}_5\mathrm{,}\cdots \mathrm{,}{v}_{n-2}$ must be in D. In that case, $v_n$ cannot be efficiently dominated, a contradiction. So $u_2\cancel{\in }D$ and $u_m\cancel{\in }D$, which means $u_1\in D$. By Lemma 1.3, $D=\left\{u_1\mathrm{,}{u}_4\mathrm{,}{u}_7\mathrm{,}\cdots \mathrm{,}{u}_{m-2}\mathrm{,}{v}_3\mathrm{,}{v}_6\mathrm{,}{v}_9\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\right\}$ is an efficient dominating set of G. Therefore, G has a unique efficient dominating set.

3) Suppose that $n=2\left(\mathrm{mod}3\right)$. If $u_1\in D$, then by Lemma 1.3, $v_3\mathrm{,}{v}_6\mathrm{,}{v}_9\mathrm{,}\cdots \mathrm{,}{v}_{n-2}$ are all in D. In that case, $v_n$ cannot be efficiently dominated, a contradiction. So $u_1\cancel{\in }D$, which means $u_2\in D$ or $u_m\in D$. By Lemma 1.3, $D=\left\{u_2\mathrm{,}{u}_5\mathrm{,}{u}_8\mathrm{,}\cdots \mathrm{,}{u}_{m-1}\mathrm{,}{v}_2\mathrm{,}{v}_5\mathrm{,}{v}_8\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ is an efficient dominating set of G if $u_2\in D$, and $D=\left\{u_3\mathrm{,}{u}_6\mathrm{,}{u}_9\mathrm{,}\cdots ,u_m\mathrm{,}{v}_2\mathrm{,}{v}_5\mathrm{,}{v}_8\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ is an efficient dominating set of G if $u_m\in D$. Therefore G has two efficient dominating sets.

Lemma 3.6. Let G be an $\left(m\mathrm{,}n\right)$ -tadpole graph, where $m\ge 3$ and $n\ge 1$.

1) If $m=2\left(\mathrm{mod}3\right)$, then G does not have an efficient dominating set.

2) If $m=1\left(\mathrm{mod}3\right)$, then G has a unique efficient dominating set if and only if $n\ne 1\mathrm{mod}3$.

Proof. Consider $u_1$ and its three neighbors $u_2$, $u_m$ and $v_1$. Exactly one of these 4 vertices is in D.

1) Suppose that $m=2\left(\mathrm{mod}3\right)$. If $u_1\in D$, then by Lemma 1.3, $u_1\mathrm{,}{u}_4\mathrm{,}{u}_7\mathrm{,}\cdots \mathrm{,}{u}_{m-1}\in D$. In that case, $u_m$ is dominated by two vertices, a contradiction. If $u_2\in D$, then by Lemma 1.3, $u_2\mathrm{,}{u}_5\mathrm{,}{u}_8\mathrm{,}\cdots ,u_m\in D$. In that case, $u_1$ is dominated by two vertices, a contradiction. By argument similar to $u_2$, $u_m\cancel{\in }D$. If $v_1\in D$, then by Lemma 1.3, $u_3\mathrm{,}{u}_6\mathrm{,}{u}_9\mathrm{,}\cdots ,u_{m-2}\in D$. In that case, $u_m$ cannot be efficiently dominated, a contradiction. Thus, G does not have an efficient dominating set.

2) Suppose that $m=1\left(\mathrm{mod}3\right)$. If $u_1\in D$, then by Lemma 1.3, $u_1\mathrm{,}{u}_4\mathrm{,}{u}_7\mathrm{,}\cdots \mathrm{,}{u}_m\in D$. Now $u_1$ and $u_m$ are both in D, a contradiction. If $u_2\in D$, then by Lemma 1.3, $u_2\mathrm{,}{u}_5\mathrm{,}{u}_8\mathrm{,}\cdots ,u_{m-2}\in D$ and then $u_m$ cannot be efficiently dominated, a contradiction. By argument similar to $u_2$, $u_m\notin D$. If $v_1\in D$, then by Lemma 1.3, $u_3\mathrm{,}{u}_6\mathrm{,}{u}_9\mathrm{,}\cdots ,u_{m-1}\in D$ and $v_4\mathrm{,}{v}_7\mathrm{,}\cdots \in D$. So only when $n\ne 0\left(\mathrm{mod}3\right)$, 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 $\left(m\mathrm{,}n\right)$ -tadpole graph, where $m\ge 3$ and $n\ge 1$. Then G has a unique efficient dominating set if and only if $m=0\left(\mathrm{mod}3\right)$ and $n=1\left(\mathrm{mod}3\right)$, or $m=1\left(\mathrm{mod}3\right)$ and $n\ne 0\left(\mathrm{mod}3\right)$.

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 $K_{\mathrm{1,}k}$ with $k\ge 2$, where $v$ is the center. The n-sunlet graph is the graph on 2n vertices obtained from a cycle $C_n=u_1{u}_2\cdots u_n{u}_1$ by attaching n pendant edges $u_i{v}_i$, $1\le i\le n$ [3]. The n-centipede graph is the graph on 2n vertices obtained from a path $P_n=u_1{u}_2\cdots u_n$ by attaching $n$ pendant edges $u_i{v}_i$, $1\le i\le n$ [3]. An $\left(n\mathrm{,}k\right)$ -firecracker is a graph obtained from n copies of k-stars by connecting $v_i{v}_{i+1}$, where $v_i$ is a leaf from the i-th star and $1\le i\le n-1$.

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 $n\ge 2$.

3) G is an $\left(n\mathrm{,}k\right)$ -firecracker with $n\mathrm{,}k\ge 2$.

Proof. 1) By Lemma 1.2 vi), the set of all the pendant vertices of an $n$ -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 $n$ -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 $u$ on the main stalk a star vertex or s-vertex if $d\left(u\right)\ge 4$, and we will call a vertex $u$ on the main stalk a p-vertex if $d\left(u\right)=3$ ( p refers to the single pendant vertex of $u$ ). Furthermore, we call a vertex $u$ on the main stalk a trivial vertex if $d\left(u\right)=2$, and a nontrivial vertex if $d\left(u\right)\ge 3$. A pair of nontrivial vertices $\left(u\mathrm{,}v\right)$ is called a pair- $n$ 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- $n$, there are at most two vertices of degree 2 between them. This implies that for a pair- $n$, there are exactly $n$ 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 $u^{\prime }$ and $v^{\prime }$ be pendant vertices connected to $u$ and $v$, respectively.

1) If $u$ and $v$ are a pair-2, then $u\mathrm{,}v\in D$.

2) If $u$ and $v$ are a pair-0, then $u^{\prime }\mathrm{,}{v}^{\prime }\in D$.

3) If $u$ and $v$ are a pair-1, then $u^{\prime }\mathrm{,}v\in D$ and $u$ is a p-vertex, or $u\mathrm{,}{v}^{\prime }\in D$ and $v$ is a p-vertex.

Proof. 1) Suppose that $u_1\mathrm{,}{v}_1$ are the two vertices of degree 2 between $u$ and $v$ such that $u{u}_1\mathrm{,}{u}_1{v}_1\mathrm{,}{v}_{1}v\in E\left(G\right)$. By Lemma 1.2 iv), $u_1\cancel{\in }D$ and $v_1\cancel{\in }D$. In order to dominate $u_1$ and $v_1$, we have $u\mathrm{,}v\in D$.

2) By Lemma 1.2 iv), $u\notin D$ and $v\notin D$. In order to dominate $u$ and $v$, it is the case that $u^{\prime }\mathrm{,}{v}^{\prime }\in D$. 3) Suppose that $u\in D$. By Lemma 1.2 i), $v\notin D$. By Lemma 1.2 iv), $v^{\prime }\in D$ and by Lemma 1.2 v), $v$ is a p-vertex. Similarly, we can prove that if $v\in D$, then $u^{\prime }\in D$ and $u$ is a p-vertex.

For the caterpillar graph G, if there are more than one p-vertices $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_s$ such that $v_i{v}_{i+1}\in E\left(G\right)$ for $1\le i\le s-1$, we will call $\left(v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_s\right)$ a cluster of pair-0.

Lemma 3.10. Let G be a caterpillar graph and $\left(u\mathrm{,}v\right)$ be a pair-2 of G. Suppose that $G^{\prime }$ is the graph obtained from G by contracting the path of length 3 between $u$ and $v$ to a single vertex w. Then G has a unique efficient dominating set D if and only if $G^{\prime }$ has a unique efficient dominating set $D\cup \left\{w\right\}-\left\{u\mathrm{,}v\right\}$.

Proof. If G has a unique efficient dominating set D, then by Lemma 3.9 1), $u\mathrm{,}v\in D$, and $D\cup \left\{w\right\}-\left\{u\mathrm{,}v\right\}$ is an efficient dominating set of $G^{\prime }$. If $G^{\prime }$ has a unique efficient dominating set $D^{\prime }$, then by Lemma 1.2 v), $w\in D^{\prime }$, and $\left(D^{\prime }-\left\{w\right\}\right)\cup \left\{u\mathrm{,}v\right\}$ 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 $G^{\prime }$. Therefore, G has a unique efficient dominating set D if and only if $G^{\prime }$ has a unique efficient dominating set $D\cup \left\{w\right\}-\left\{u\mathrm{,}v\right\}$.

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 $u$ and $v$ (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 $u$ and $v$ be two neighboring s-vertices (no other s-vertices in between). By Lemma 1.2 v), $u$ and $v$ are both in D. Based on the assumption d), there are only pair-1 and pair-0 between $u$ and $v$. Then there must be an even number of pair-1 between $u$ and $v$. 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 $u$ and the last vertex $v$ 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 $u$ and $v$ are two neighboring nontrivial vertices (no other nontrivial vertices in between) of G such that $u$ is a vertex in a cluster of pair-0 and $v$ is a vertex in another cluster of pair-0. By Lemma 3.9 2), $u^{\prime }\in D$ and $v^{\prime }\in D$, where $u^{\prime }$ is the pendant vertex adjacent to $u$ and $v^{\prime }$ is the pendant vertex adjacent to $v$. There must be even number of trivial vertices (vertices of degree 2) between $u$ and $v$. So 3) is true.

Suppose that $u$ and $v$ are two neighboring nontrivial vertices (no other nontrivial vertices in between) of G such that $u$ is an s-vertex and $v$ is a vertex in a cluster of pair-0. Since $u\in D$ and $v^{\prime }\in D$, where $v^{\prime }$ is the pendant vertex adjacent to $v$, there must be odd number of trivial vertices (vertices of degree 2) between $u$ and $v$. 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 $u$ and G has no cluster of pair-0. So all the nontrivial vertices of G except $u$ are all p-vertices and G has pair-1 only. By Lemma 1.2 v), $u\in D$. By Lemma 3.9 3), the efficient dominating set of G is uniquely determined based on the fact that $u\in D$.

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 $1\le i\le n$, let $L_i=v_0^i{v}_1^i{v}_2^i\cdots v_{l_i}^i$ and let $S\left(v\mathrm{,}{l}_1\mathrm{,}{l}_2\mathrm{,}{l}_3\mathrm{,}\cdots \mathrm{,}{l}_n\right)$ be the graph generated from $L_1\mathrm{,}{L}_2\mathrm{,}\cdots \mathrm{,}{L}_n$ by identifying $v_0^1\mathrm{,}{v}_0^2\mathrm{,}\cdots \mathrm{,}{v}_0^n$ as a single vertex $v$. Then $S\left(v\mathrm{,}{l}_1\mathrm{,}{l}_2\mathrm{,}{l}_3\mathrm{,}\cdots \mathrm{,}{l}_n\right)$ is called a spider graph with center $v$ and $n$ legs, where $l_i$ denotes the length and the number of vertices on the ith leg. If $n=\mathrm{1,2}$, then S is just a path. Thus, the following theorems assume that S has at least 3 legs, that is, $n\ge 3$.

Lemma 3.12. Let G denote the spider graph $S\left(v\mathrm{,}{l}_1\mathrm{,}{l}_2\mathrm{,}{l}_3\mathrm{,}\cdots \mathrm{,}{l}_n\right)$ with center $v$ and $n$ legs, where $l_i$ denotes the length of the ith leg. If G has a unique efficient dominating set D, then the following statements are true.

1) If $v\in D$, then $l_i\ne 2\left(\mathrm{mod}3\right)$.

2) If $v_1^i\in D$, then $l_i\ne 0\left(\mathrm{mod}3\right)$.

3) If $v_1^i\in D$, then $l_j\ne 1\left(\mathrm{mod}3\right)$ for any $j\ne i$.

Proof. 1) Suppose that $v\in D$. If $l_i=2\left(\mathrm{mod}3\right)$, then $v_3^i\mathrm{,}{v}_6^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i-2}^i\in D$. In this case, $v_{l_i}^i$ is not dominated by any vertex in D, a contradiction.

2) Suppose that $v_1^i\in D$. If $l_i=0\left(\mathrm{mod}3\right)$, then $v_4^i\mathrm{,}{v}_7^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i-2}^i\in D$. In this case, $v_{l_i}^i$ is not dominated by any vertex in D, a contradiction.

3) Suppose that $v_1^i\in D$. If $l_j=1\left(\mathrm{mod}3\right)$, then $v_2^j\mathrm{,}{v}_5^j\mathrm{,}\cdots \mathrm{,}{v}_{l_j-2}^j\in D$. In this case, $v_{l_j}^j$ is not dominated by any vertex in D, a contradiction.

Lemma 3.13. Let G denote the spider graph $S\left(v\mathrm{,}{l}_1\mathrm{,}{l}_2\mathrm{,}{l}_3\mathrm{,}\cdots \mathrm{,}{l}_n\right)$ with center $v$ and n legs, where $l_i$ denotes the length of the $i$ th leg.

1) If $l_i=0\left(\mathrm{mod}3\right)$ for $1\le i\le n$, then G has a unique efficient dominating set.

2) If $l_i=1\left(\mathrm{mod}3\right)$ for $1\le i\le n$, then G has a unique efficient dominating set.

3) If $l_i=2\left(\mathrm{mod}3\right)$ for $1\le i\le n$, then G has n efficient dominating sets.

Proof. 1) By definition, G is generated from $L_1\mathrm{,}{L}_2\mathrm{,}\cdots \mathrm{,}{L}_n$ by identifying $v_0^1\mathrm{,}{v}_0^2\mathrm{,}\cdots \mathrm{,}{v}_0^n$ as a single vertex $v$. Since $l_1\mathrm{,}{l}_2\mathrm{,}\cdots \mathrm{,}{l}_n$ are all equal to 0 mod 3, it is the case that $L_1\mathrm{,}{L}_2\mathrm{,}\cdots \mathrm{,}{L}_n$ are all paths with number of vertices equal to 1 (mod 3). By Theorem 3.1 2), for each $1\le i\le n$, $L_i$ has a unique efficient dominating set $D_i=\left\{v_0^i,v_3^i,v_6^i,\cdots ,v_{l_i}^i\right\}$. By Theorem 2.3, G has a unique efficient dominating set $D=D_1\cup D_2\cup D_3\cup \cdots \cup D_n$, where we consider $v_0^1=v_0^2=v_0^3=\cdots =v_0^n=v$.

2) Consider the star graph $K_{\mathrm{1,}n}$ with center $v$. The center $v$ has $n$ neighbors $v_1^1\mathrm{,}{v}_1^2\mathrm{,}\cdots \mathrm{,}{v}_1^n$. By Lemma 1.2 v), $\left\{v\right\}$ is the efficient dominating set. For $1\le i\le n$, define $P_{k_i}=v_2^i{v}_3^i\cdots v_{l_i}^i$. Then, $k_i=l_i-1=0\left(\mathrm{mod}3\right)$ vertices. By Lemma 3.1 1), $P_{k_i}$ has a unique efficient dominating set $D_i=\left\{v_3^i,v_6^i,v_9^i,\cdots ,v_{l_i-1}^i\right\}$. Since G can be constructed from the star graph $K_{\mathrm{1,}n}$ and $P_{k_i}$, where $1\le i\le n$, by connecting $v_1^i$ to $v_2^i$, by Theorem 2.1, G has a unique dominating set $D=\left\{v\right\}\cup D_1\cup D_2\cup D_3\cup \cdots \cup D_n$.

3) Let D be an efficient dominating set of G. If $v\in D$, then for $1\le i\le n$, $v_3^i\mathrm{,}{v}_6^i\mathrm{,}\cdots \mathrm{,}{v}_{n-2}^i\in D$ and then $v_n^i$ is not dominated by any vertex in D, a contradiction. Therefore, $v\cancel{\in }D$. Since $v\cancel{\in }D$, one of $v_1^1\mathrm{,}{v}_1^2\mathrm{,}{v}_1^3\mathrm{,}\cdots \mathrm{,}{v}_1^n$ must be in D. If $v_1^i\in D$, then $D_i=\left\{v_2^1,v_5^1,\cdots ,v_{l_n}^1\right\}\cup \left\{v_2^2,v_5^2,\cdots ,v_{l_2}^2\right\}\cup \cdots \cup \left\{v_1^i,v_4^i,\cdots ,v_{l_i-1}^i\right\}\cup \cdots \cup \left\{v_2^n,v_5^n,\cdots ,v_{l_n}^n\right\}$. Thus, G has n efficient dominating sets.

In the following proof, a Type-n leg is defined to be a leg with $n$ mod 3 vertices, not counting the vertex that becomes the center.

Theorem 3.14. Let G denote the spider graph $S\left(v\mathrm{,}{l}_1\mathrm{,}{l}_2\mathrm{,}{l}_3\mathrm{,}\cdots \mathrm{,}{l}_n\right)$ with center $v$ and $n$ legs, where $l_i$ denotes the length of the $i$ 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 $L_i=v{v}_1^i{v}_2^i\cdots v_{l_i}^i$ and $L_j=v{v}_1^j{v}_2^j\cdots v_{l_j}^j$ be two Type-2 legs. By Lemma 3.12 1), $v\cancel{\in }D$. Let $L_k=v{v}_1^k{v}_2^k\cdots v_{l_k}^k$ be the leg of G such that $v_1^k$ dominates $v$. By Lemma 3.12 2), $L_k$ is not a Type-0 leg and so $L_k$ must be a Type-2 leg. If $L_m$ is a Type-2 leg with $m\ne k$, then $v_2^m\mathrm{,}{v}_5^m\mathrm{,}\cdots \mathrm{,}{v}_{l_m}\in D$ ; if $L_m$ is a Type-0 leg, then $v_2^m\mathrm{,}{v}_5^m\mathrm{,}\cdots \mathrm{,}{v}_{l_m-1}\in D$ ; for the Type-2 leg $L_k$, $v_1^k\mathrm{,}{v}_4^k\mathrm{,}{v}_7^k\mathrm{,}\cdots \mathrm{,}{v}_{l_k-1}\in D$. 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 $v\in D$, then $v_3^i\mathrm{,}{v}_6^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i}^i\in D$ if $L_i$ is a Type-0 leg and $v_3^i\mathrm{,}{v}_6^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i-1}^i\in D$ if $L_i$ is a Type-1 leg. If $v\cancel{\in }D$, then $v_2^i\mathrm{,}{v}_5^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i-1}^i\in D$ if $L_i$ is a Type-0 leg and $v_1^i\mathrm{,}{v}_4^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i}^i\in D$ if $L_i$ 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 $L_i=v{v}_1^i{v}_2^i\cdots v_{l_i}^i$ and $L_j=v{v}_1^j{v}_2^j\cdots v_{l_j}^j$ be two Type-1 legs. By Lemma 3.12 3), $v\in D$. Suppose that G has a Type-2 leg $L_k=v{v}_1^k{v}_2^k\cdots v_{l_k}^k$. Then by Lemma 1.3, $v_3^k\mathrm{,}{v}_6^k\mathrm{,}\cdots \mathrm{,}{v}_{l_k-2}^k\in D$. In this case, $v_{l_k}^k$ 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), $v\cancel{\in }D$. Then there is $v_1^j\in D$. By Lemma 3.12 2), $L_j$ is not a Type-0 leg. Since G doesn’t have Type-1 legs, $L_j$ must be the Type-2 leg. So for any Type-0 leg $L_i$, $v_2^i\mathrm{,}{v}_5^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i-1}^i\in D$, and for the Type-2 leg $L_j$, $v_1^j\mathrm{,}{v}_4^j\mathrm{,}\cdots \mathrm{,}{v}_{l_j-1}^j\in D$. 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), $v\cancel{\in }D$. Then there is $v_1^j\in D$. By Lemma 3.12 2), $L_j$ is not a Type-0 leg and by Lemma 3.12 3), $L_j$ is not a Type-2 leg. So $L_j$ must be the Type-1 leg. So for any Type-0 leg $L_i$, $v_2^i\mathrm{,}{v}_5^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i-1}^i\in D$, for the Type-1 leg $L_j$, $v_1^j\mathrm{,}{v}_4^j\mathrm{,}\cdots \mathrm{,}{v}_{l_j}^j\in D$, and for any Type-2 leg $L_k$, $v_2^k\mathrm{,}{v}_5^k\mathrm{,}\cdots \mathrm{,}{v}_{l_k}^k\in D$. 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), $v_1^i\cancel{\in }D$ for any $i$. So $v\in D$ and for any Type-0 leg $L_i$, $v_3^i\mathrm{,}{v}_6^i\mathrm{,}\cdots \mathrm{,}{v}_{l_i}^i\in D$, and for the Type-1 leg $L_j$, $v_3^j\mathrm{,}{v}_6^j\mathrm{,}\cdots \mathrm{,}{v}_{l_j-1}^j\in D$. Thus, G has a unique efficient dominating set.

3.4. Further Discussion

Theorem 3.15. Let G be a graph with independent set $D=\left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_t\right\}$ such that 1) $V\left(G\right)\backslash D=N\left(u_1\right)\stackrel{\dot{}}{\cup }N\left(u_2\right)\stackrel{\dot{}}{\cup }\cdots \stackrel{\dot{}}{\cup }N\left(v_t\right)$ and 2) for every vertex in $x\in N\left(u_i\right)$ and $y\in N\left(u_j\right)$, $xy\in E\left(G\right)$. Then $D=\left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots ,u_t\right\}$ is the unique efficient dominating set of G.

Proof. Based on the fact that D is an independent set and every vertex in $V\left(G\right)\backslash D$ 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 $D^{\prime }$ is an efficient dominating set. Suppose that $u_1\cancel{\in }{D}^{\prime }$. Then there must be a vertex $v_1\in N\left(u_1\right)$ such that $v_1\in D^{\prime }$. Since $D^{\prime }$ is independent, no vertex of $N\left(u_2\right)$ can be an element of $D^{\prime }$. Since $d\left(v_1\mathrm{,}{u}_2\right)=2$, $u_2$ is not in $D^{\prime }$ (Otherwise, every vertex in $N\left(u_2\right)$ is dominated by $v_1$ and $u_2$ ). Now $u_2$ is not dominated by any vertex of $D^{\prime }$. Therefore $u_1\in D^{\prime }$. Similarly, $u_i\in D^{\prime }$ for any $i$. So $D\subseteq D^{\prime }$. By Theorem 1.1, $D=D^{\prime }$. So D is the unique efficient dominating set of G.

Corollary 3.16. Let G be a graph obtained from $K_{s_1\mathrm{,}{s}_2\mathrm{,}\cdots \mathrm{,}{s}_t}=\left(V_1\mathrm{,}{V}_2\mathrm{,}\cdots ,V_t\right)$ by adding $u_i$ and connecting $u_i$ to each vertex in $V_i$ for $i=\mathrm{1,2,}\cdots \mathrm{,}t$. Then $D=\left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots ,u_t\right\}$ is the unique efficient dominating set of G.

Corollary 3.17. Let G be a graph obtained from $K_n$ by adding $u_i$ and connecting $u_i$ to each vertex in $V_i$ for $i=\mathrm{1,2,}\cdots \mathrm{,}t$, where $V\left(K_n\right)=V_1\stackrel{\dot{}}{\cup }{V}_2\stackrel{\dot{}}{\cup }\cdots \stackrel{\dot{}}{\cup }{V}_t$. Then $D=\left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots ,u_t\right\}$ is the unique efficient dominating set of G.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Mostaghim, Z. and Kjalkhali, A.S. (2012) Efficient Dominating Sets in Ladder Graphs. International Journal of Engineering Research and Development, 2, 42-43.
[2]	Hedetniemi, J. (2017) On Graphs Having a Unique Minimum Independent Dominating Set. Australian Journal of Combinatorics, 68, 357-370.
[3]	Wolfram MathWorld (2019). http://mathworld.wolfram.com/