The Generalization of Signed Domination Number of Two Classes of Graphs

Xia Hong¹, Guoyan Ao², Feng Gao¹

¹Department of Mathematics, Luoyang Normal University, Luoyang, China.
²School of Mathematics and Statistics, Hulunbuir University, Inner Mongolia, China.

DOI: 10.4236/ojdm.2021.114009                

Abstract

Let be a graph. A function is said to be a Signed Dominating Function (SDF) if holds for all . The signed domination number . In this paper, we determine the exact value of the Signed Domination Number of graphs and for , which is generalized the known results, respectively, where and are denotes the k-th power graphs of cycle and path .

Keywords

Signed Domination Function, Signed Domination Numbers, Graphs C_n^k, Graphs P_n^k

1. Introduction

The graphs considered in this paper are finite, undirected, and simple (no loops or multiple edges). For notation and graph theory terminology, please refer to the reference [1]. Let G be a simple undirected graph. The vertex set and the edge set of G are denoted by $V\left(G\right)$ and $E\left(G\right)$, respectively. For a vertex $v\in V\left(G\right)$, the neighbor set $N_G\left(v\right)$ is the set of vertices adjacent to v, the degree of v is the number of adjacent vertices of v and denoted by $d_G\left(v\right)$. $\delta \left(G\right)=\min \left\{d_G\left(v\right)\mathrm{<mo>\; :\; </mo>}v\in V\left(G\right)\right\}$ and $\Delta \left(G\right)=\max \left\{d_G\left(v\right):v\in V\left(G\right)\right\}$ is the minimum degree and maximum degree of G. When no confusion can occur, we shall write $N\left(v\right)\mathrm{,}N\left[v\right]\mathrm{,}\Delta \mathrm{,}\delta$, instead of $N_G\left(v\right)\mathrm{,}{N}_G\left[v\right]\mathrm{,}\Delta \left(G\right)\mathrm{,}\delta \left(G\right)$. For a subset $U\subseteq V\left(G\right)$, the subgraph induced by U is denoted by $G\left[U\right]$, which is the graph on U whose edges are precisely the edges of G with both ends in U.

For $u\in V\left(G\right)$ and $U\subseteq V\left(G\right)$, the distance between u and U, denoted by $d_G\left(u\mathrm{,}U\right)$, is the length of a shortest path from u to a vertex in U. When U consists of a single vertex v, we write $d_G\left(u\mathrm{,}v\right)$, instead of $d_G\left(u\mathrm{,}\left\{v\right\}\right)$. For a positive integer k, the k-th power $G^k$ of a graph G is the graph $G^k$ whose vertex set is $V\left(G\right)$, two distinct vertices being adjacent in $G^k$ if and only if their distance in G is at most k. If $k=1$, $G^1=G$. In particular, the graph $G^2$ and the graph $G^3$ are as the square of G and the cube of G. A cycle on $n\left(n\ge 3\right)$ vertices is a graph whose vertices can be arranged in a cyclic sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise, denoted by $C_n$. A path $P_n$ is a simple graph whose vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise.

In recent years, several kinds of signed domination problems in graphs have been investigated [2] [3] [4] [5]. Most of those belong to the vertex domination (or edge domination) of graphs, such as signed (edge) domination [6] [7], minus domination [8], cycle domination [9], signed roman (total) domination [10], weak roman domination [11], inverse signed total domination [12], etc. The signed domination number of cycles $C_n$, paths $P_n$, the square $C_n^2$ of $C_n$ and the square $P_n^2$ of $P_n$ were given in [13] [14] [15], respectively. In the present paper, we compute the exact values of signed domination number of $C_n^k$ and $P_n^k$ for $k\ge 1$.

Let $G=\left(V\mathrm{,}E\right)$ be a graph and $ℝ$ be a real set. For a real function $f\mathrm{<mo>\; :\; </mo>}V\to R$ and a nonempty subset $S\subseteq V\left(G\right)$, we may assume that $f\left(S\right)={\displaystyle {\sum }_{v\in S}}f\left(v\right)$. In the following, for the sake of simplicity, simply write $f\left(N\left[v\right]\right)$ as $f\left[v\right]$, denotes $f\left(V\right)=f\left(V\left(G\right)\right)$. In addition, $\lceil x\rceil$ and $\lfloor x\rfloor$ denotes the smallest integer not less than x and the largest integer not greater than x.

2. Preliminaries

Definition 1. [4] Let $G=\left(V\mathrm{,}E\right)$ be a graph, a function $f\mathrm{<mo>\; :\; </mo>}V\to \left\{-\mathrm{1,1}\right\}$ is said to be a Signed Dominating Function (SDF) if $f\left[v\right]={\displaystyle {\sum }_{v\in N\left[u\right]}}f\left(v\right)\ge 1$ holds for all $u\in V$, the signed domination number: ${\gamma }_s\left(G\right)=\min \left\{{\displaystyle {\sum }_{v\in V}}f\left(v\right)|fisanSEDofG\right\}$.

By Definition 1, it is easy to see the following a conclusion.

Lemma 1. For any vertex $v\in V\left(G\right)$ and an SED f of G, if $d_G\left(v\right)$ is even, then $f\left[v\right]\ge 1$. If $d_G\left(v\right)$ is odd, then $f\left[v\right]\ge 2$.

For some vertex $v_i$, it is called a optimal if $f\left[v_i\right]$ is reach it’s lower bound.

Lemma 2. [8] Let $P_n$ be a path. For $n\ge 2$, we have ${\gamma }_s\left(P_n\right)=n-2\lfloor \frac{n-2}{3}\rfloor$.

Lemma 3. [13] Let $C_n$ be a cycle. For $n\ge 3$ , we have ${\gamma }_s\left(C_n\right)=n-2\lceil \frac{n-2}{3}\rceil$.

Lemma 4. [13] If $K_n$ is a complete graph, then:

${\gamma }_s\left(K_n\right)=\{\begin{array}{ll}1,\hfill & n\equiv 1\left(mod2\right)\hfill \\ 2,\hfill & n\equiv 0\left(mod2\right)\hfill \end{array}$

Lemma 5. [14] If $C_n^2$ is a square of $C_n$, then:

${\gamma }_s\left(C_n^2\right)=\{\begin{array}{ll}\lceil \frac{n}{5}\rceil ,\hfill & n\equiv 0,1,3\left(mod5\right)\hfill \\ \lceil \frac{n}{5}\rceil +1,\hfill & n\equiv 2,4\left(mod5\right)\hfill \end{array}$

Lemma 6. [15] For a square $P_n^2$ of $P_n$, if $n=3$, then ${\gamma }_s\left(P_3^2\right)=1$. If $n\ge 4$, then:

${\gamma }_s\left(P_n^2\right)=\{\begin{array}{ll}0.2\left(n+12\right),\hfill & n=5k+3\hfill \\ 0.2\left(n+4\right),\hfill & n=5k+1\hfill \\ 0.2\left(n+6\right),\hfill & n=5k+\mathrm{4\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mtext>\; \hspace{0.17em}\; </mtext>}k\in N\hfill \\ 0.2n,\hfill & n=5k\hfill \\ 0.2\left(n+8\right),\hfill & n=5k+2\hfill \end{array}$

Lemma 7. [13] If G is a r-regular graph on n order, then ${\gamma }_s\left(G\right)\ge \frac{n}{r+1}$.

In this paper, we give an exact value of signed domination number of $C_n^k$ and $P_n^k$ for $k\ge 1$ as follows.

Theorem 1. Let $C_n^k$ be a k-th power graph of cycle $C_n$ . For $n\ge \mathrm{3,}k\ge 1$, we have: :

${\gamma }_s\left(C_n^k\right)=\{\begin{array}{ll}\lceil \frac{n}{2k+1}\rceil ,\hfill & ifn\equiv 0,1,3,\cdots ,2k-1\left(mod2k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +1,\hfill & ifn\equiv 2,4,\cdots ,2k\left(mod2k+1\right)\hfill \end{array}$

If $k=1$ in Theorem 1, then it is equal to Lemma 3. If $k=2$ in theorem 1, then it is equal to Lemma 5.

Theorem 2. Let $P_n^k$ be a k-th power graph of path $P_n$ . For $n\ge 2$, $1\le k\le n-1$, we have the following results.

If $1\le k\le \lfloor \frac{n}{2}\rfloor -1$ and k is odd, then:

${\gamma }_s\left(P_n^k\right)=\{\begin{array}{ll}\lceil \frac{n}{2k+1}\rceil +2,\hfill & ifn\equiv 0,1,\cdots ,2k-1\left(mod2k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +1,\hfill & ifn\equiv 2,4,\cdots ,2k\left(mod2k+1\right)\hfill \end{array}$

If $1\le k\le \lfloor \frac{n}{2}\rfloor -1$ and k is even, then:

${\gamma }_s\left(P_n^k\right)=\{\begin{array}{ll}\lceil \frac{n}{2k+1}\rceil ,\hfill & ifn\equiv 0,1\left(mod2k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +1,\hfill & ifn\equiv 2,4,\cdots ,2k\left(mod2k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +2,\hfill & ifn\equiv 3,5,\cdots ,2k-1\left(mod2k+1\right)\hfill \end{array}$

If $\lfloor \frac{n}{2}\rfloor \le k\le n-1\left(n\ne \mathrm{3,}k\ne 1\right)$, then:

${\gamma }_s\left(P_n^k\right)=\{\begin{array}{ll}1,\hfill & ifn\equiv 1\left(mod2\right)\hfill \\ 2,\hfill & ifn\equiv 0\left(mod2\right)\hfill \end{array}$

If $n=3,k=1$,then ${\gamma }_s\left(P_3\right)=3$.

In fact, if $k=1$ in Theorem 2, then it is equal to Lemma 2. If $k=2$ in theorem 2, then it is equal to Lemma 6.

3. Proof of Theorems

3.1. Proof of Theorem 1

Proof. Let $C_n^k$ be a k-th power graph of cycle $C_n$. By definition of k-th power graph, it is easy to see that $C_n^k$ is a 2k-regular graph. By symmetry of cycle, it is

enough to show that $k\le \frac{n}{2}$. It remains to show that it is true for $1\le k\le \frac{n}{2}$. By Lemma 1, we have ${\gamma }_s\left(C_n^k\right)\ge \lceil \frac{n}{2k+1}\rceil$. We may assume that G has t vertices

with −1 label and s vertices with +1 label, then $s+t=n$, ${\gamma }_s\left(G\right)=n-2t$. Let $n=\left(2k+1\right)q+r$, $0\le r\le 2k$.

If $r=0$, then ${\gamma }_s\left(C_n^k\right)\ge \lceil \frac{n}{2k+1}\rceil$.

If $r=1,3,\cdots ,2k-1$, then ${\gamma }_s\left(C_n^k\right)\ge \lceil \frac{n}{2k+1}\rceil$.

If $r=2,4,\cdots ,2k$, then ${\gamma }_s\left(C_n^k\right)\ge \lceil \frac{n}{2k+1}\rceil =q+1$. If n is odd, then q is odd, and $q+1$ is even. But ${\gamma }_s\left(C_n^k\right)=n-2t$ is odd and therefore: ${\gamma }_s\left(C_n^k\right)\ge \lceil \frac{n}{2k+1}\rceil +1=q+2$. If n is even, then q is even, and $q+1$ is odd. But ${\gamma }_s\left(C_n^k\right)=n-2t$ is even and therefore ${\gamma }_s\left(C_n^k\right)\ge \lceil \frac{n}{2k+1}\rceil +1=q+2$.

In summary, we have:

${\gamma }_s\left(C_n^k\right)\ge \{\begin{array}{ll}\lceil \frac{n}{2k+1}\rceil \mathrm{,}\hfill & n\equiv \mathrm{0,1,}\cdots \mathrm{,2}k-1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +\mathrm{1,}\hfill & n\equiv \mathrm{2,4,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \end{array}$

By definition of singed domination number, we only need to give a singed domination function f of $C_n^k$. Let $C_n$ be a cycle on n vertices $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n$.

If $n\equiv 0\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}+\mathrm{1,}\hfill & \text{if}i\equiv \mathrm{1,3,}\cdots \mathrm{,2}k+1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ -\mathrm{1,}\hfill & \text{if}n\equiv \mathrm{2,4,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \end{array}$

It is easy to see that $C_n^k$ has a $t=k\cdot \frac{n}{2k+1}$ vertices with −1 label and $n-t$ vertices with +1 label. It is follows that:

$f\left(V\right)=n-2\left(k\cdot \frac{n}{2k+1}\right)=n-2k\cdot \frac{n}{2k+1}=\lceil \frac{n}{2k+1}\rceil$.

So, we have ${\gamma }_s\left(C_n^k\right)=\lceil \frac{n}{2k+1}\rceil$.

If $n\equiv \mathrm{1,3,}\cdots \mathrm{,2}k-1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}+\mathrm{1,}\hfill & \text{if}i\equiv \mathrm{1,3,4,6,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ -\mathrm{1,}\hfill & \text{if}n\equiv \mathrm{2,5,7,}\cdots \mathrm{,2}k+1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \end{array}$

By the definition of f, for every $2k+1$ consecutive vertices on the $C_n^k$, there

are k vertices that can be signed as −1, and $\lfloor \frac{r}{2}\rfloor$ of the remaining $n-r$ vertices can be signed as −1. So, it is easy to see that $C_n^k$ has a $t=k\cdot \lfloor \frac{n}{2k+1}\rfloor +\lfloor \frac{n-\left(2k+1\right)\lfloor \frac{n}{2k+1}\rfloor }{2}\rfloor$ vertices with −1 label and $n-t$ vertices with +1 label. It is follows that: $\begin{array}{c}f\left(V\right)=n-2\left(k\cdot \lfloor \frac{n}{2k+1}\rfloor +\lfloor \frac{n-\left(2k+1\right)\lfloor \frac{n}{2k+1}\rfloor }{2}\rfloor \right)\\ =n-2k\cdot \lfloor \frac{n}{2k+1}\rfloor -\left(n-\left(2k+1\right)\lfloor \frac{n}{2k+1}\rfloor -1\right)\\ =\lfloor \frac{n}{2k+1}\rfloor +1=\lceil \frac{n}{2k+1}\rceil \end{array}$.

So, we have ${\gamma }_s\left(C_n^k\right)=\lceil \frac{n}{2k+1}\rceil$.

If $n\equiv \mathrm{2,4,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}+\mathrm{1,}\hfill & \text{if}i\equiv \mathrm{1,2,4,6,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ -\mathrm{1,}\hfill & \text{if}n\equiv \mathrm{3,5,7,}\cdots \mathrm{,2}k+1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \end{array}$

Same as above, it is easy to see that $C_n^k$ has a $t=k\cdot \lfloor \frac{n}{2k+1}\rfloor +\frac{n-\left(2k+1\right)\lfloor \frac{n}{2k+1}\rfloor -2}{2}$ vertices with −1 label and $n-t$ vertices with +1 label. It is follows that: $\begin{array}{c}f\left(V\right)=n-2\left(k\cdot \lfloor \frac{n}{2k+1}\rfloor +\frac{n-\left(2k+1\right)\lfloor \frac{n}{2k+1}\rfloor -2}{2}\right)\\ =n-2k\cdot \lfloor \frac{n}{2k+1}\rfloor -n+\left(2k+1\right)\lfloor \frac{n}{2k+1}\rfloor +2\\ =\lfloor \frac{n}{2k+1}\rfloor +2=\lceil \frac{n}{2k+1}\rceil +1\end{array}$.

So, we have ${\gamma }_s\left(C_n^k\right)=\lceil \frac{n}{2k+1}\rceil +1$.

As mentioned above, we have:

${\gamma }_s\left(C_n^k\right)\mathrm{<mo>\; =\; </mo>}\{\begin{array}{ll}\lceil \frac{n}{2k+1}\rceil \mathrm{,}\hfill & n\equiv \mathrm{0,1,}\cdots \mathrm{,2}k-1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +\mathrm{1,}\hfill & n\equiv \mathrm{2,4,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \end{array}$ $\square$

3.2. Proof of Theorem 2

Proof. Let $P_n^k$ be a k-th power graph of $P_n$, denoted by G. By definition of k-th power graph, we may assume that the vertex set of G are $\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$, its edge set are $\left\{E_1\mathrm{,}{E}_2\mathrm{,}\cdots \mathrm{,}{E}_{n-1}\right\}$, where:

$E_j=\left\{v_i{v}_{i+j}\mathrm{<mo>\; |\; </mo>1}\le i\le n-j\right\}\mathrm{,1}\le j\le n-1$.

It is follows that:

$d_G\left(v_j\right)=d_G\left(v_{n-j+1}\right)=k+j-1,j=1,\cdots ,k$

$d_G\left(v_{k+1}\right)=\cdots =d_G\left(v_{n-k}\right)=2k.$

If $n=2$, then $k=1$. So, ${\gamma }_s\left(P_2\right)=2$.

If $n=3$, then $k=1$ (or $k=2$ ). So, ${\gamma }_s\left(P_3\right)=3$ (or 1).

It remains to show that it is true for $n\ge 4$.

Case 1. $\lfloor \frac{n}{2}\rfloor \le k\le n-1$.

We first prove that it is true for the lower bound of signed domination number of $P_n^k$. If $k\ge \lfloor \frac{n}{2}\rfloor$, then $d_G\left(v_{\lceil \frac{n}{2}\rceil }\right)=n-1$. If n is odd, then: $f\left(V\right)=f\left(v_1\right)+f\left(v_2\right)+\cdots +f\left(v_n\right)=f\left[v_{\lceil \frac{n}{2}\rceil }\right]\ge 1$. So, ${\gamma }_s\left(G\right)\ge 1$. If n is even, then $f\left(V\right)=f\left(v_1\right)+f\left(v_2\right)+\cdots +f\left(v_n\right)=f\left[v_{\frac{n}{2}}\right]\ge 1$. In such a case, since $d_G\left(v_{\frac{n}{2}}\right)=n-1$ is odd and $\left|f\left[v_{\frac{n}{2}}\right]\right|$ is even. By Lemma 1, we have $f\left(V\right)\ge 2$. So, ${\gamma }_s\left(G\right)\ge 2$.

We only need to give a singed domination function f and prove that it is true for the upper bound of signed domination number of $P_n^k$.

Subcase 1.1. $n\equiv 1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 4}\right)$.

Due to $\delta =d_G\left(v_1\right)=k\ge \lfloor \frac{n}{2}\rfloor$, $\left|f\left[v_1\right]\right|=k+1\ge \lfloor \frac{n}{2}\rfloor +1$ and $\lfloor \frac{n}{2}\rfloor$ is even. It follows that we are labeled −1 at $t=\lfloor \frac{n}{4}\rfloor$ vertices in $f\left[v_1\right]$ and in $f\left[v_n\right]$, and other vertices is label to +1. Namely, let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,t,n-t+1,n-t+2,\cdots ,n\hfill \\ +1,\hfill & \text{otherwise}\hfill \end{array}$

It is easy to show that $f\left[v_j\right]\ge \mathrm{1,}f\left[v_{n-j+1}\right]\ge 1$ for $j=1,\cdots ,\lfloor \frac{n}{2}\rfloor$ and $f\left[v_{\lceil \frac{n}{2}\rceil }\right]=1$. In fact, under this function f, we have: $f\left(V\right)=f\left[v_{\lceil \frac{n}{2}\rceil }\right]=f\left(v_1\right)+f\left(v_2\right)+\cdots +f\left(v_n\right)=n-4t=n-4\left(\lfloor \frac{n}{4}\rfloor \right)=1$. So, ${\gamma }_s\left(G\right)\le 1$.

In summary, we have ${\gamma }_s\left(G\right)=1$.

Subcase 1.2. $n\equiv 2\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 4}\right)$.

Because of $\delta =d_G\left(v_1\right)=k\ge \lfloor \frac{n}{2}\rfloor$, $\left|f\left[v_1\right]\right|=k+1\ge \lfloor \frac{n}{2}\rfloor +1$ and $\lfloor \frac{n}{2}\rfloor$ is odd. It follows that we are labeled −1 at $t=\lfloor \frac{n}{4}\rfloor$ vertices in $f\left[v_1\right]$ and in $f\left[v_n\right]$, and other vertices is label to +1. Namely, let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,t,n-t+1,n-t+2,\cdots ,n\hfill \\ +1,\hfill & \text{otherwise}\hfill \end{array}$

It is easy to show that $f\left[v_j\right]\ge \mathrm{1,}f\left[v_{n-j+1}\right]\ge 1$ for $j=1,\cdots ,\frac{n}{2}-1$ and $f\left[v_{\frac{n}{2}}\right]=f\left[v_{\frac{n}{2}+1}\right]=2$. In fact, under this function f, we have: $\begin{array}{c}f\left(V\right)=f\left[v_{\frac{n}{2}}\right]=f\left(v_1\right)+f\left(v_2\right)+\cdots +f\left(v_n\right)\\ =n-4t=n-4\left(\lfloor \frac{n}{4}\rfloor \right)=n-4\left(\frac{n-2}{4}\right)=2\end{array}$. So ${\gamma }_s\left(G\right)\le 2$.

In summary, we have ${\gamma }_s\left(G\right)=2$.

Subcase 1.3. $n\equiv 3\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 4}\right)$.

Thanks to $\delta =d_G\left(v_1\right)=k\ge \lfloor \frac{n}{2}\rfloor$, $\left|f\left[v_1\right]\right|=k+1\ge \lfloor \frac{n}{2}\rfloor +1$ and $\lfloor \frac{n}{2}\rfloor$ is odd. It follows that we are labeled −1 at $t_1=\lceil \frac{n}{4}\rceil -1$ vertices in $f\left[v_1\right]$ and labeled −1 at $t_2=\lfloor \frac{n}{4}\rfloor -1$ vertices in $f\left[v_n\right]$, and other vertices is label to +1. Namely, let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,t_1,n-t_2+1,n-t_2+2,\cdots ,n\hfill \\ +1,\hfill & \text{otherwise}\hfill \end{array}$

It is easy to show that $f\left[v_j\right]\ge \mathrm{1,}f\left[v_{n-j+1}\right]\ge 1$ for $j=1,\cdots ,\lfloor \frac{n}{2}\rfloor$ and $f\left[v_{\lceil \frac{n}{2}\rceil }\right]=1$. In fact, under this function f, we have: $\begin{array}{c}f\left(V\right)=f\left[v_{\lceil \frac{n}{2}\rceil }\right]=f\left(v_1\right)+f\left(v_2\right)+\cdots +f\left(v_n\right)\\ =n-2\left(t_1+t_2\right)=n-2\lceil \frac{n}{4}\rceil -2\lfloor \frac{n}{4}\rfloor =n-\frac{n+1}{2}-\frac{n-3}{2}=1\end{array}$. So, ${\gamma }_s\left(G\right)\le 1$.

In summary, we have ${\gamma }_s\left(G\right)=1$.

Subcase 1.4. $n\equiv 0\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 4}\right)$.

Since $\delta =d_G\left(v_1\right)=k\ge \lfloor \frac{n}{2}\rfloor$, $\left|f\left[v_1\right]\right|=k+1\ge \lfloor \frac{n}{2}\rfloor +1$ and $\lfloor \frac{n}{2}\rfloor$ is even. It follows that we are labeled −1 at $t_1=\frac{n}{4}$ vertices in $f\left[v_1\right]$ and labeled −1 at $t_2=\frac{n}{4}-1$ vertices in $f\left[v_n\right]$, and other vertices is label to +1. Namely, let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,t_1,n-t_2+1,n-t_2+2,\cdots ,n\hfill \\ +1,\hfill & \text{otherwise}\hfill \end{array}$

It is easy to show that $f\left[v_j\right]\ge \mathrm{1,}f\left[v_{n-j+1}\right]\ge 1$ for $j=1,\cdots ,\frac{n}{2}-1$ and $f\left[v_{\frac{n}{2}}\right]=f\left[v_{\frac{n}{2}+1}\right]=2$. In fact, under this function f, we have: $\begin{array}{c}f\left(V\right)=f\left[v_{\frac{n}{2}}\right]=f\left(v_1\right)+f\left(v_2\right)+\cdots +f\left(v_n\right)\\ =n-2\left(t_1+t_2\right)=n-2\left(2\cdot \frac{n}{4}-1\right)=n-4\cdot \frac{n}{4}+2=2\end{array}$. So, ${\gamma }_s\left(G\right)\le 2$.

In summary, we have ${\gamma }_s\left(G\right)=2$.

Case 2. $1\le k\le \lceil \frac{n}{2}\rceil -1$.

Subcase 2.1. $n\equiv 1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)$.

We first prove that it is true for the lower bound of signed domination number of $P_n^k$.

If k is odd, then $\left|f\left[v_1\right]\right|=k+1$ is even. By Lemma 1, we have: $f\left[v_1\right]={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)\ge 2$, $f\left[v_n\right]={\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\ge 2$. It is follows that: $\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(2k+2\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+1}\right]+{\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\\ \ge 2+\frac{n-\left(2k+2\right)}{2k+1}+2=4+\frac{n-\left(2k+2\right)}{2k+1}\\ =\frac{n-1}{2k+1}+\frac{6k+3}{2k+1}=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. So, we have: ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +2$.

If k is even, then $\left|f\left[v_1\right]\right|=k+1$ is odd. By Lemma 1, we have: $f\left[v_1\right]={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)\ge 1$, $f\left[v_n\right]={\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\ge 1$. It is follows that: $\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(2k+2\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+1}\right]+{\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\\ \ge 1+\frac{n-\left(2k+2\right)}{2k+1}+1=2+\frac{n-\left(2k+2\right)}{2k+1}=\frac{n-1}{2k+1}+1=\lceil \frac{n}{2k+1}\rceil \end{array}$. So, we have: ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil$.

On the other hand, we only need to give a signed domination function f.

If k is odd, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\lfloor \frac{k}{2}\rfloor ,k+2+q\left(2k+1\right),k+4+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 3k+q\left(2k+1\right),n-\lfloor \frac{k}{2}\rfloor +1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\lfloor \frac{k}{2}\rfloor +1,\cdots ,k+1,k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 3k+1+q\left(2k+1\right),3k+2+q\left(2k+1\right),n-k,\cdots ,n-\lfloor \frac{k}{2}\rfloor \hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+1\right)}{2k+1}-1$. It is easy to see that G has a $t=2\cdot \lfloor \frac{k}{2}\rfloor +k\cdot \frac{n-2\left(k+1\right)}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \lfloor \frac{k}{2}\rfloor +k\cdot \frac{n-2\left(k+1\right)}{2k+1}\right]\\ =n-2k+2-2k\cdot \frac{n-2k-2}{2k+1}=\frac{n+2k}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. So, we have ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil +2$.

If k is even, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\frac{k}{2},k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 3k+1+q\left(2k+1\right),n-\frac{k}{2}+1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\frac{k}{2}+1,\cdots ,k+1,k+2+q\left(2k+1\right),k+4+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 3k+2+q\left(2k+1\right),n-k,\cdots ,n-\frac{k}{2}\hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+1\right)}{2k+1}-1$. It is easy to see that G has a $t=2\cdot \frac{k}{2}+k\cdot \frac{n-2\left(k+1\right)}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \frac{k}{2}+k\cdot \frac{n-2\left(k+1\right)}{2k+1}\right]\\ =n-2k-2k\cdot \frac{n-2k-2}{2k+1}=\frac{n+2k}{2k+1}=\lceil \frac{n}{2k+1}\rceil \end{array}$. So, we have: ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil$.

Subcase 2.2. $n\equiv 0\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)$.

We first prove that it is true for the lower bound of signed domination number of $P_n^k$.

If k is odd, then $\left|f\left[v_1\right]\right|=k+1$ is even. By Lemma 1, we have: $f\left[v_1\right]={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)\ge 2$, $f\left[v_n\right]={\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\ge 2$, ${\displaystyle {\sum }_{i=n-k-2k}^{n-k-1}}f\left(v_i\right)\ge 0$ (otherwise, we have $f\left[v_{n-2k}\right]\le 0$, this is a contradiction to Definition 1). It is follows that

$\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(2k+2+2k\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+1}\right]+{\displaystyle {\sum }_{i=n-k-2k}^{n-k-1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\\ \ge 2+\frac{n-\left(2k+2+2k\right)}{2k+1}+0+2=4+\frac{n-4k-2}{2k+1}=\frac{n}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. So, we have ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +2$.

If k is even, then $\left|f\left[v_1\right]\right|=k+1$ is odd. By Lemma 1, we have $f\left[v_1\right]={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)\ge 1$, $f\left[v_n\right]={\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\ge 1$, ${\displaystyle {\sum }_{i=n-k-2k}^{n-k-1}}f\left(v_i\right)\ge 0$ (otherwise, we have $f\left[v_{n-2k}\right]\le 0$, this is a contradiction to Definition 1). It is follows that

$\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(2k+2+2k\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+1}\right]+{\displaystyle {\sum }_{i=n-k-2k}^{n-k-1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\\ \ge 1+\frac{n-\left(2k+2+2k\right)}{2k+1}+0+1=2+\frac{n-4k-2}{2k+1}=\lceil \frac{n}{2k+1}\rceil \end{array}$. So, we have ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil$.

On the other hand, we only need to give a signed domination function f.

If k is odd, then let

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\lfloor \frac{k}{2}\rfloor ,k+2+q\left(2k+1\right),k+4+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 3k+q\left(2k+1\right),n-\lfloor \frac{k}{2}\rfloor +1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\lfloor \frac{k}{2}\rfloor +1,\cdots ,k+1,k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 3k+1+q\left(2k+1\right),3k+2+q\left(2k+1\right),n-k,\cdots ,n-\lfloor \frac{k}{2}\rfloor \hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+1\right)-2k}{2k+1}$. Specially, if $q=\frac{n-2\left(k+1\right)-2k}{2k+1}$, then $f\left(v_q\right)=f\left(v_{n-k}\right)$ and all such vertices are label to +1. Then G has a $t=2\cdot \lfloor \frac{k}{2}\rfloor +k+k\cdot \frac{n-2\left(k+1\right)-2k}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that: $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \lfloor \frac{k}{2}\rfloor +k+k\cdot \frac{n-2\left(k+1\right)-2k}{2k+1}\right]\\ =n-2\left(k-1\right)-2k-2k\cdot \frac{n-4k-2}{2k+1}\\ =n-4k+2-2k\cdot \frac{n-4k-2}{2k+1}=\frac{n}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. So, we have: ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil +2$.

If k is even, then:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\frac{k}{2},k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & \begin{array}{l}2k+1+q\left(2k+1\right),2k+2+q\left(2k+1\right),\cdots ,\\ 2k+2+\frac{k}{2}-1+q\left(2k+1\right),n-\frac{k}{2}+1,\cdots ,n\end{array}\hfill \\ +1,\hfill & \text{if}i=\frac{k}{2}+1,\cdots ,k+1,k+2+q\left(2k+1\right),k+4+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 2k+q\left(2k+1\right),2k+2+\frac{k}{2}+q\left(2k+1\right),\cdots ,3k+1+q\left(2k+1\right),\hfill \\ \hfill & 3k+2+q\left(2k+1\right),n-k,\cdots ,n-\frac{k}{2}\hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+1\right)-2k}{2k+1}$. Specially, if $q=\frac{n-2\left(k+1\right)-2k}{2k+1}$, then $f\left(v_q\right)=f\left(v_{n-k}\right)$ and all such vertices are label to +1. Then G has a $t=2\cdot \frac{k}{2}+k+k\cdot \frac{n-2\left(k+1\right)-2k}{2k+1}$ vertices with −1 and other vertex is label to +1. It is follows that $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \frac{k}{2}+k+k\cdot \frac{n-2\left(k+1\right)-2k}{2k+1}\right]\\ =n-2k-2k-2k\cdot \frac{n-4k-2}{2k+1}=\frac{n}{2k+1}=\lceil \frac{n}{2k+1}\rceil \end{array}$. So, we have ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil$.

Subcase 2.3. $n\equiv 2\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)$.

We first prove that it is true for the lower bound of signed domination number of $P_n^k$.

If k is odd, then $\left|f\left[v_1\right]\right|=k+1$ is even. By Lemma 1, we have:

$f\left[v_1\right]={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)\ge 2$, $f\left[v_n\right]={\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\ge 2$, $f\left(v_{n-k-1}\right)\ge -1$. It is follows that $\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(2k+2+1\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+1}\right]+f\left(v_{n-k-1}\right)+{\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\\ \ge 2+\frac{n-\left(2k+2+1\right)}{2k+1}-1+2=3+\frac{n-2k-3}{2k+1}=\frac{n-2}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +1$.

If k is even, then $\left|f\left[v_2\right]\right|$ is even. By Lemma 1, we have:

$f\left[v_2\right]={\displaystyle {\sum }_{i=1}^{k+2}}f\left(v_i\right)\ge 2$, $f\left[v_n\right]={\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\ge 1$, ${\displaystyle {\sum }_{i=n-k-2k-1}^{n-k-1}}f\left(v_i\right)\ge 1$. It is follows that $\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+2}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(2k+4+2k\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+2}\right]\\ +{\displaystyle {\sum }_{i=n-k-2k-1}^{n-k-2}}f\left(v_i\right)+{\displaystyle {\sum }_{i=n-k-1}^n}f\left(v_i\right)\\ \ge 2+\frac{n-\left(2k+4+2k\right)}{2k+1}+1+1=4+\frac{n-4k-4}{2k+1}\\ =\frac{n-2}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have:

${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +1$.

On the other hand, we only need to give a signed domination function f.

If k is odd, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\lfloor \frac{k}{2}\rfloor ,k+2+q\left(2k+1\right),k+4+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 2k-1+q\left(2k+1\right),2k+1+q\left(2k+1\right),2k+2+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 3k-1+q\left(2k+1\right),n-k-1,n-\lfloor \frac{k}{2}\rfloor +1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\lfloor \frac{k}{2}\rfloor +1,\cdots ,k+1,k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 2k+q\left(2k+1\right),2k+3+q\left(2k+1\right),\cdots ,3k+q\left(2k+1\right),\hfill \\ \hfill & 3k+1+q\left(2k+1\right),3k+2+q\left(2k+1\right),n-k,\cdots ,n-\lfloor \frac{k}{2}\rfloor \hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+1\right)-1}{2k+1}-1$. It is easy to see that G has a $t=2\cdot \lfloor \frac{k}{2}\rfloor +1+k\cdot \frac{n-2\left(k+1\right)-1}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \lfloor \frac{k}{2}\rfloor +1+k\cdot \frac{n-2\left(k+1\right)-1}{2k+1}\right]\\ =n-2k-2k\cdot \frac{n-2k-3}{2k+1}=\frac{n+4k}{2k+1}=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil +1$.

If k is even, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\frac{k}{2},k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & \begin{array}{l}2k+1+q\left(2k+1\right),2k+3+q\left(2k+1\right),\cdots ,\\ 2k+\frac{k}{2}+2+q\left(2k+1\right),n-\frac{k}{2}+1,\cdots ,n\end{array}\hfill \\ +1,\hfill & \text{if}i=\frac{k}{2}+1,\cdots ,k+2,k+4+q\left(2k+1\right),k+6+q\left(2k+1\right),\cdots ,\hfill \\ \hfill & 2k+2+q\left(2k+1\right),2k+\frac{k}{2}+3+q\left(2k+1\right),\cdots ,3k+2+q\left(2k+1\right),\hfill \\ \hfill & 3k+3+q\left(2k+1\right),n-k-1,\cdots ,n-\frac{k}{2}\hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+2\right)-2k}{2k+1}$. Specially, if $q=\frac{n-2\left(k+2\right)-2k}{2k+1}$, then $f\left(v_q\right)=f\left(v_{n-k-1}\right)$ and all such vertices are label to +1. It is easy to see that G has a $t=2\cdot \frac{k}{2}+k+k\cdot \frac{n-2\left(k+2\right)-2k}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that: $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \frac{k}{2}+k+k\cdot \frac{n-2\left(k+2\right)-2k}{2k+1}\right]\\ =n-2k-2k-2k\cdot \frac{n-4k-4}{2k+1}=\frac{n+4k}{2k+1}=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have: ${\gamma }_s\left(G\right)\mathrm{<mo>\; =\; </mo>}\lceil \frac{n}{2k+1}\rceil +1$.

Subcase 2.4. $n\equiv r\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\mathrm{,}r=\mathrm{3,5,7,}\cdots \mathrm{,2}k-1$.

We first prove that it is true for the lower bound of signed domination number of $P_n^k$.

Claim. Let $P_n=v_1{v}_2\cdots v_n$ be a path and f be an SED of $P_n^k$. If every vertex $v_i\left(1\le i\le n-r\right)$ is optimal, then $f\left(v_{\left(2k+1\right)q}\right)=-1$, where $q=1,\cdots ,\frac{n-r}{2k+1}$.

Proof: If k is odd, then $\left|f\left[v_1\right]\right|=k+1$ is even. Since every vertex $v_i$ is

optimal, by Lemma 1, we have $f\left[v_1\right]=2$. It is follows that $f\left[v_1\right]$ has $\lfloor \frac{k}{2}\rfloor$ vertices with −1 label, $f\left[v_3\right]$ has $\lfloor \frac{k}{2}\rfloor +1$ vertices with −1 label, $\cdots$, $f\left[v_k\right]$ has $\lfloor \frac{k}{2}\rfloor +\lfloor \frac{k}{2}\rfloor$ vertices with −1 label. Because of $f\left[v_{k+1}\right]=f\left[v_k\right]+f\left(v_{2k+1}\right)$,

and $v_{k+1}$ is optimal and therefore $f\left[v_{k+1}\right]$ has k vertices with −1 label. So, we have $f\left(v_{2k+1}\right)=-1$.

If k is even, then $\left|f\left[v_1\right]\right|=k+2$ is even. Since every vertex $v_i$ is optimal, by Lemma 1, we have $f\left[v_2\right]=2$. It is follows that $f\left[v_2\right]$ has $\frac{k}{2}$ vertices with −1

label, $f\left[v_4\right]$ has $\frac{k}{2}+1$ vertices with −1 label, $\cdots$, $f\left[v_k\right]$ has $\frac{k}{2}+\frac{k}{2}-1$ vertices with −1 label. Due to $f\left[v_{k+1}\right]=f\left[v_k\right]+f\left(v_{2k+1}\right)$, and $v_{k+1}$ is optimal and

therefore $f\left[v_{k+1}\right]$ has k vertices with −1 label. So, we have $f\left(v_{2k+1}\right)=-1$.

We consider that every vertex $v_i$ is optimal and the following facts.

$f\left[v_{k+1}\right]={\displaystyle {\sum }_{i=1}^{2k+1}}f(\; v\; i\; )$

$f\left[v_{k+2+\left(2k+1\right)\cdot j}\right]=f\left[v_{k+1+\left(2k+1\right)\cdot j}\right]-f\left(v_{1+\left(2k+1\right)\cdot j}\right)+f\left(v_{2k+2+\left(2k+1\right)\cdot j}\right)$

$f\left[v_{k+3+\left(2k+1\right)\cdot j}\right]=f\left[v_{k+2+\left(2k+1\right)\cdot j}\right]-f\left(v_{2+\left(2k+1\right)\cdot j}\right)+f\left(v_{2k+3+\left(2k+1\right)\cdot j}\right)$

…

$f\left[v_{3k+2+\left(2k+1\right)\cdot j}\right]=f\left[v_{3k+1+\left(2k+1\right)\cdot j}\right]-f\left(v_{2k+1+\left(2k+1\right)\cdot j}\right)+f\left(v_{4k+2+\left(2k+1\right)\cdot j}\right)$

where $j=0,\cdots ,\frac{n-r-2k-1}{2k+1}-1$

It is follows that:

$f\left(v_1\right)=f\left(v_{2k+2}\right)=f\left(v_{4k+3}\right)=\cdots =f\left(v_{1+\left(2k+1\right)\left(q-1\right)}\right)$

$f\left(v_2\right)=f\left(v_{2k+3}\right)=f\left(v_{4k+4}\right)=\cdots =f\left(v_{2+\left(2k+1\right)\left(q-1\right)}\right)$

…

$f\left(v_{2k+1}\right)=f\left(v_{4k+2}\right)=f\left(v_{6k+3}\right)=\cdots =f\left(v_{2k+1+\left(2k+1\right)\left(q-1\right)}\right)$

where $q=1,\cdots ,\frac{n-r}{2k+1}$

So, we have:

$f\left(v_{\left(2k+1\right)q}\right)=-1$.

Subsubcase 2.4.1. If $r\le k+1$, then $k+r\le 2k+1$.

If k is odd, then $\left|f\left[v_n\right]\right|=k+1$ is even and $f\left[v_n\right]={\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\ge 2$. So, ${\displaystyle {\sum }_{i=1}^{k+r}}f\left(v_i\right)=f\left[v_r\right]\ge 2$. It is follows that:

$\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+r}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(k+1+k+r\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+r}\right]+{\displaystyle {\sum }_{i=n-k}^n}f\left(v_i\right)\\ \ge 2+\frac{n-\left(k+1+k+r\right)}{2k+1}+2=4+\frac{n-2k-r-1}{2k+1}\\ =\frac{n-r}{2k+1}+3=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. Hence, ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +2$.

If k is even, then $\left|f\left[v_{n-1}\right]\right|=k+2$ is even and $f\left[v_{n-1}\right]={\displaystyle {\sum }_{i=n-k-1}^n}f\left(v_i\right)\ge 2$. So, ${\displaystyle {\sum }_{i=1}^{k+r-1}}f\left(v_i\right)\ge 2$. It is follows that:

$\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+r-1}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(k+2+k+r-1\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+r-1}\right]+{\displaystyle {\sum }_{i=n-k-1}^n}f\left(v_i\right)\\ \ge 2+\frac{n-\left(k+1+k+r\right)}{2k+1}+2=4+\frac{n-2k-r-1}{2k+1}\\ =\frac{n-r}{2k+1}+3=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. Hence, ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +2$.

Subsubcase 2.4.2. If $r>k+1$, then $k+r>2k+1$.

It is follows that $f\left(V\right)={\displaystyle {\sum }_{i=1}^{\frac{n-r}{2k+1}}}f\left[v_{\left(2k+1\right)i-k}\right]+{\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)$. Owing to

${\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\ge 3$ (Otherwise, since r is odd and therefore ${\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\le 1$. In order to obtain the ${\gamma }_s\left(P_n^k\right)$, we have to consider that all vertices are as optimal as possible. By Claim, we have $f\left(v_{\left(2k+1\right)q}\right)=-1$, namely, $f\left(v_{n-r}\right)=-1$. So, $f\left[v_{n-k+1}\right]=f\left(v_{n-r}\right)+{\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\le -1+1=0$, this is a contradiction to Definition 1).

Hence, $f\left(V\right)={\displaystyle {\sum }_{i=1}^{\frac{n-r}{2k+1}}}f\left[v_{\left(2k+1\right)i-k}\right]+{\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\ge \frac{n-r}{2k+1}+3=\lceil \frac{n}{2k+1}\rceil +2$.

On the other hand, we only need to give a signed domination function f.

If k is odd, then we give a signed domination function f by the following rules.

If $1\le i\le k+1$ and $n-k\le i\le n$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\lfloor \frac{k}{2}\rfloor ,n-\lfloor \frac{k}{2}\rfloor +1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\lfloor \frac{k}{2}\rfloor +1,\cdots ,k+1,n-k,\cdots ,n-\lfloor \frac{k}{2}\rfloor \hfill \end{array}$

If $k+2\le i\le n-k-1$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=k+2+q\left(2k+1\right),k+4+q\left(2k+1\right),\cdots ,3k+q\left(2k+1\right)\hfill \\ +1,\hfill & \text{if}i=k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,3k+1+q\left(2k+1\right),\hfill \\ \hfill & 3k+2+q\left(2k+1\right)\hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+1\right)-\left(r-1\right)}{2k+1}$. It is trivial to see that G has a $t=2\cdot \lfloor \frac{k}{2}\rfloor +\lfloor \frac{r}{2}\rfloor +k\cdot \frac{n-2\left(k+1\right)-\left(r-1\right)}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that: $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \lfloor \frac{k}{2}\rfloor +\frac{r-1}{2}+k\cdot \frac{n-2\left(k+1\right)-\left(r-1\right)}{2k+1}\right]\\ =n-2k+2-2k\cdot \frac{n-2k-\left(r-1\right)}{2k+1}-\left(r-1\right)\\ =\frac{n-r}{2k+1}+3=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. So, we have: ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil +2$.

If k is even, then we give a signed domination function f by the following rules.

If $1\le i\le k+2$ and $n-k-1\le i\le n$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\frac{k}{2},n-\frac{k}{2}+1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\frac{k}{2}+1,\cdots ,k+2,n-k-1,\cdots ,n-\frac{k}{2}\hfill \end{array}$

If $k+3\le i\le n-k-2$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,3k+1+q\left(2k+1\right)\hfill \\ +1,\hfill & \text{if}i=k+4+q\left(2k+1\right),k+6+q\left(2k+1\right),\cdots ,3k+2+q\left(2k+1\right),\hfill \\ \hfill & 3k+3+q\left(2k+1\right)\hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+2\right)-\left(r-3\right)}{2k+1}$. It is trivial to see that G has a $t=2\cdot \frac{k}{2}+\frac{r-3}{2}+k\cdot \frac{n-2\left(k+2\right)-\left(r-3\right)}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that: $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \frac{k}{2}+\frac{r-3}{2}+k\cdot \frac{n-2\left(k+2\right)-\left(r-3\right)}{2k+1}\right]\\ =n-2k-\left(r-3\right)-2k\cdot \frac{n-2k-r-1}{2k+1}=\frac{n-r}{2k+1}+3=\lceil \frac{n}{2k+1}\rceil +2\end{array}$. So, we have: ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil +2$.

Subcase 2.5. $n\equiv r\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\mathrm{,}r=\mathrm{2,4,6,}\cdots \mathrm{,2}k$.

We first prove that it is true for the lower bound of signed domination number of $P_n^k$.

Subsubcase 2.5.1 If $r\le k+1$, then $k+r\le 2k+1$.

If k is odd, then $\left|f\left[v_{n-2}\right]\right|=k+3$ is even and $f\left[v_{n-2}\right]={\displaystyle {\sum }_{i=n-k-2}^n}f\left(v_i\right)\ge 2$. Hence, ${\displaystyle {\sum }_{i=1}^{k+r-2}}f\left(v_i\right)\ge 1$. It is follows that:

$\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+r-2}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(k+3+k+r-2\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+r-2}\right]+{\displaystyle {\sum }_{i=n-k-2}^n}f\left(v_i\right)\\ \ge 1+\frac{n-\left(2k+r+1\right)}{2k+1}+2=3+\frac{n-2k-r-1}{2k+1}=\frac{n-r}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +1$.

If k is even, then $\left|f\left[v_{n-1}\right]\right|=k+2$ is even and $f\left(v_{n-k-2}\right)\ge -1$, $f\left[v_{n-1}\right]={\displaystyle {\sum }_{i=n-k-1}^n}f\left(v_i\right)\ge 2$. Hence, ${\displaystyle {\sum }_{i=1}^{k+r-2}}f\left(v_i\right)\ge 2$. It is follows that:

$\begin{array}{c}f\left(V\right)={\displaystyle {\sum }_{i=1}^{k+r-2}}f\left(v_i\right)+{\displaystyle {\sum }_{i=1}^{\frac{n-\left(k+2+k+r-2+1\right)}{2k+1}}}f\left[v_{\left(2k+1\right)i+r-2}\right]\\ +f\left(v_{n-k-2}\right)+{\displaystyle {\sum }_{i=n-k-1}^n}f\left(v_i\right)\\ \ge 2+\frac{n-\left(2k+1+r\right)}{2k+1}-1+2\\ =3+\frac{n-2k-r-1}{2k+1}=\frac{n-r}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have: ${\gamma }_s\left(G\right)\ge \lceil \frac{n}{2k+1}\rceil +1$.

Subsubcase 2.5.2. If $r>k+1$, then $k+r>2k+1$.

It is follows that $f\left(V\right)={\displaystyle {\sum }_{i=1}^{\frac{n-r}{2k+1}}}f\left[v_{\left(2k+1\right)i-k}\right]+{\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)$. Because of

${\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\ge 2$ (Otherwise, we have ${\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\le 1$. In order to obtain the ${\gamma }_s\left(P_n^k\right)$, we have to consider that all vertices are as optimal as possible. By Claim, we have $f\left(v_{\left(2k+1\right)q}\right)=-1$, namely, $f\left(v_{n-r}\right)=-1$. It follows that: $f\left[v_{n-k+1}\right]=f\left(v_{n-r}\right)+{\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\le -1+1=0$, this is a contradiction to Definition 1).

Hence, $f\left(V\right)={\displaystyle {\sum }_{i=1}^{\frac{n-r}{2k+1}}}f\left[v_{\left(2k+1\right)i-k}\right]+{\displaystyle {\sum }_{i=n-r+1}^n}f\left(v_i\right)\ge \frac{n-r}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +1$.

On the other hand, we only need to give a signed domination function f.

If k is odd, then we give a signed domination function f by the following rules.

If $1\le i\le k+1$ and $n-k\le i\le n$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\lfloor \frac{k}{2}\rfloor ,n-\lfloor \frac{k}{2}\rfloor +1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\lfloor \frac{k}{2}\rfloor +1,\cdots ,k+1,n-k,\cdots ,n-\lfloor \frac{k}{2}\rfloor \hfill \end{array}$

If $k+2\le i\le n-k-1$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=k+2+q\left(2k+1\right),k+4+q\left(2k+1\right),\cdots ,3k+q\left(2k+1\right)\hfill \\ +1,\hfill & \text{if}i=k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,3k+1+q\left(2k+1\right),\hfill \\ \hfill & 3k+2+q\left(2k+1\right)\hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+1\right)-\left(r-1\right)}{2k+1}$. It is trivial to see that G has a $t=2\cdot \lfloor \frac{k}{2}\rfloor +\lceil \frac{r-1}{2}\rceil +k\cdot \frac{n-2\left(k+1\right)-\left(r-1\right)}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that: $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \lfloor \frac{k}{2}\rfloor +\frac{r}{2}+k\cdot \frac{n-2\left(k+1\right)-\left(r-1\right)}{2k+1}\right]\\ =n-2k+2-r-2k\cdot \frac{n-2k-r-1}{2k+1}=\frac{n-r}{2k+1}+1=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil +1$.

If k is even, then we give a a signed domination function f by the following rules.

If $1\le i\le k+2$ and $n-k-1\le i\le n$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=1,\cdots ,\frac{k}{2},n-\frac{k}{2}+1,\cdots ,n\hfill \\ +1,\hfill & \text{if}i=\frac{k}{2}+1,\cdots ,k+2,n-k-1,\cdots ,n-\frac{k}{2}\hfill \end{array}$

If $k+3\le i\le n-k-2$, then let:

$f\left(v_i\right)=\{\begin{array}{ll}-1,\hfill & \text{if}i=k+3+q\left(2k+1\right),k+5+q\left(2k+1\right),\cdots ,3k+1+q\left(2k+1\right)\hfill \\ +1,\hfill & \text{if}i=k+4+q\left(2k+1\right),k+6+q\left(2k+1\right),\cdots ,3k+2+q\left(2k+1\right),\hfill \\ \hfill & 3k+3+q\left(2k+1\right)\hfill \end{array}$

where $q=0,\cdots ,\frac{n-2\left(k+2\right)-\left(r-3\right)}{2k+1}$. It is trivial to see that G has a $t=2\cdot \frac{k}{2}+\lceil \frac{r-3}{2}\rceil +k\cdot \frac{n-2\left(k+2\right)-\left(r-3\right)}{2k+1}$ vertices with −1 label and other vertex is label to +1. It is follows that: $\begin{array}{c}{\gamma }_s\left(G\right)\le f\left(V\right)=n-2\left[2\cdot \frac{k}{2}+\frac{r-2}{2}+k\cdot \frac{n-2k-r-1}{2k+1}\right]\\ =n-2k-r+2-2k\cdot \frac{n-2k-r-1}{2k+1}=\frac{n-r}{2k+1}+2=\lceil \frac{n}{2k+1}\rceil +1\end{array}$. So, we have ${\gamma }_s\left(G\right)=\lceil \frac{n}{2k+1}\rceil +1$.

As mentioned above, we have:

If $1\le k\le \lfloor \frac{n}{2}\rfloor -1$ and k is odd, then:

${\gamma }_s\left(P_n^k\right)=\{\begin{array}{ll}\lceil \frac{n}{2k+1}\rceil +\mathrm{2,}\hfill & \text{if}n\equiv \mathrm{0,1,}\cdots \mathrm{,2}k-1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +\mathrm{1,}\hfill & \text{if}n\equiv \mathrm{2,4,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \end{array}$

If $1\le k\le \lfloor \frac{n}{2}\rfloor -1$ and k is even, then:

${\gamma }_s\left(P_n^k\right)=\{\begin{array}{ll}\lceil \frac{n}{2k+1}\rceil \mathrm{,}\hfill & \text{if}n\equiv \mathrm{0,1}\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +\mathrm{1,}\hfill & \text{if}n\equiv \mathrm{2,4,}\cdots \mathrm{,2}k\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \\ \lceil \frac{n}{2k+1}\rceil +\mathrm{2,}\hfill & \text{if}n\equiv \mathrm{3,5,}\cdots \mathrm{,2}k-1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}k+1\right)\hfill \end{array}$

If $\lfloor \frac{n}{2}\rfloor \le k\le n-1\left(n\ne \mathrm{3,}k\ne 1\right)$, then:

${\gamma }_s\left(P_n^k\right)=\{\begin{array}{ll}\mathrm{1,}\hfill & \text{if}n\equiv 1\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}\right)\hfill \\ \mathrm{2,}\hfill & \text{if}n\equiv 0\left(mod\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; 2}\right)\hfill \end{array}$

If $n=3,k=1$, then ${\gamma }_s\left(P_3\right)=3$. $\square$

4. Concluding Remarks

As the dominance theory of graphs becomes more and more diversified, the dominance problem of graphs is NP-complete. Therefore, studying the upper and lower bounds of domination numbers of graphs and even accurate estimation and mutual relations are the main aspects of current research. In this paper, we determine the exact value of the Signed Domination Number of k-th power graphs $C_n^k$ and $P_n^k$ for $k\ge 1$, these conclusions are the basis for the study of the bounds of the signed domination number of the k-th power graphs of generally connected graphs, which have important meanings in the structural theory of graph theory. From the signed domination number of the k-th power graph, other types of domination numbers can be further studied, which will be the key research object in the future.

Supported

This research is supported by NSFC (11701257); (2020xjgj016); 2020ZKYB04, Basic Research Foundation of Henan Educational Committee (20ZX004), the Young Backbone Teachers in Henan Province (Grant 2020GGJS194, 2019GGJS202) (2020-JSJYYB-053); the Young Backbone Teachers in Luoyang Normal College (2019XJGGJS-10).

Conflicts of Interest

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

References

[1]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. GTM 244, Springer, London.
[2]	Gao, H., Cao, H. and Yang, Y. (2018) On the Total Signed Domination Number of . Ars Combinatoria, 136, 3-19.
[3]	Li, W., Huang, Z., Feng, Z. and Wu, D. (2017) 2-Signed Total Domination Number of Graphs. Journal of Jiangsu Normal University, 35, 31-33. (In Chinese)
[4]	Xu, B. (2008) Control Theory of Graphs. Science Press, Beijing. (In Chinese)
[5]	Zelinka, B. (2001) Signed Total Domination Number of a Graph. Czechoslovak Mathematical Journal, 51, 225-229. https://doi.org/10.1023/A:1013782511179
[6]	Ebrahimi, B.J., Jahanbakht, N. and Mahmoodianc, E.S. (2009) Vertex Domination of Generalized Petersen Graphs. Discrete Mathematics, 309, 4355-4361. https://doi.org/10.1016/j.disc.2009.01.018
[7]	Xu, B. (2001) On Signed Edge Domination Numbers of Graphs. Discrete Mathematics, 239, 179-189. https://doi.org/10.1016/S0012-365X(01)00044-9
[8]	Dunbar, J., Hedetniemi, S., Henning, M.A. and Mcrae, A.A. (1996) Minus Domination in Regular Graphs. Discrete Mathematics, 149, 311-312. https://doi.org/10.1016/0012-365X(94)00329-H
[9]	Pi, X.M. (2018) On the Characterization of Maximal Planar Graphs with a Given Signed Cycle Domination Number. Acta Mathematica Sinica, English Series, 34, 911-920. https://doi.org/10.1007/s10114-017-6283-3
[10]	Zhao, Y. and Miao, L. (2017) Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels. Communications in Mathematical Research, 33, 318-326.
[11]	Alhevaz, A., Darkooti, M., Rahbani, H. and Shang, Y. (2019) Strong Equality of Perfect Roman and Weak Roman Domination in Trees. Mathematics, 7, Article No. 997. https://doi.org/10.3390/math7100997
[12]	Mojdeh, D.A. and Samadi, B. (2017) On the Inverse Signed Total Domination Number in Graphs. Opuscula Mathematica, 37, 447-456. https://doi.org/10.7494/OpMath.2017.37.3.447
[13]	Yu, C. and Xu, B. (1997) Signed Domination Number in Graphs. Journal of East China Jiaotong University, 14, 54-58, 67. (In Chinese)
[14]	Ding, D. (2012) The Signed Domination Number of Graph. Journal of Yichun College, 34, 21-23. (Chinese)
[15]	Kong, X., Xu, B. and Chuanming, L. (2013) The Signed Domination Numbers of Some Special Graphs. Journal of Science of Teacher’s College and University, 33, 5-7. (In Chinese)