Let \(D\) be a finite simple digraph with vertex set \(V(D)\). For \(v\in V(D)\), the set \(N^-[v]\) consists of \(v\) and all vertices of \(D\) from which arcs go into \(v\). Let \(k\ge 1\) be an integer. A signed double Roman \(k\)-dominating function (SDR\(k\)DF) on a digraph \(D\) is a function \(f:V(D)\rightarrow\{-1,1,2,3\}\) satisfying the following conditions: (i) \(\sum\limits_{x\in N^-[v]}f(x)\ge k\) for each \(v\in V(D)\); (ii) every vertex \(u\) with \(f(u)=-1\) has an in-neighbor \(z\) with \(f(z)=3\) or two in-neighbors \(x\) and \(y\) with \(f(x)=f(y)=2\); (iii) every vertex \(u\) with \(f(u)=1\) has an in-neighbor \(z\) with \(f(z)\ge 2\). The weight of an SDR\(k\)DF \(f\) is \(\omega(f)=\sum\limits_{v\in V(D)}f(v)\). The signed double Roman \(k\)-domination number \(\gamma_{sdR}^k(D)\) is the minimum weight of an SDR\(k\)DF on \(D\). In this paper, we study the signed double Roman \(k\)-domination number of digraphs and present various bounds on \(\gamma_{sdR}^k(D)\). In addition, we determine this parameter for several classes of digraphs. Some of our results extend well-known properties of the signed double Roman \(k\)-domination number \(\gamma_{sdR} ^k(G)\) of graphs \(G\).
In this paper we continue the study of signed Roman dominating functions in graphs and digraphs, introduced and investigated by Ahangar, Henning, Löwenstein, Zhao and Samodivkin [3]. Since then several variations and generalizations have been studied (see, for example, the survey articles [5, 6, 7, 8, 9, 10]).
Let \(k\ge 1\) be an integer, \(G\) a simple graph with vertex set \(V(G)\) and \(N[v]=N_G[v]\) the closed neighborhood of the vertex \(v\). A signed double Roman \(k\)-dominating function (SDR\(k\)DF) on a graph \(G\) is defined in [4] as a function \(f:V(G)\rightarrow \{-1,1,2,3\}\) such that \(\sum\limits_{x\in N_G[v]}f(x)\ge k\) for every \(v\in V(G)\), every vertex \(u\) with \(f(u)=-1\) is adjacent to a vertex \(z\) with \(f(z)=3\) or adjacent to two vertices \(x\) and \(y\) with \(f(x)=f(y)=2\), and every vertex \(u\) with \(f(u)=1\) is adjacent to a vertex \(z\) with \(f(z)\ge 2\). The weight of an SDR\(k\)DF \(f\) on a graph \(G\) is \(\omega(f)=\sum\limits_{v\in V(G)}f(v)\). The signed double Roman \(k\)-domination number \(\gamma_{sdR}^k(G)\) of \(G\) is the minimum weight of an SDR\(k\)DF on \(G\). The special case \(k=1\) has been studied in [1, 2].
Let now \(D\) be a finite and simple digraph with vertex set \(V(D)\) and arc set \(A(D)\). The integers \(n=n(D)=|V(D)|\) and \(m=m(D)=|A(D)|\) are the order and the size of the digraph \(D\), respectively. The sets \(N^+_D(v)=N^+(v)=\{x\;|\;(v,x)\in A(D)\}\) and \(N^-_D(v)=N^-(v)=\{x\;|\;(x,v)\in A(D)\}\) are called the out-neighborhood and in-neighborhood of the vertex \(v\), respectively. The corresponding closed neighborhoods are \(N^+_D[v]=N^+[v]=N^+(v)\cup\{v\}\) and \(N^-_D[v]=N^-[v]=N^-(v)\cup\{v\}\). We write \(d^+_D(v)=d^+(v)=|N^+(v)|\) for the out-degree of a vertex \(v\) and \(d^-_D(v)=d^-(v)=|N^-(v)|\) for its in-degree. The minimum and maximum in-degree are \(\delta^-=\delta^-(D)\) and \(\Delta^-=\Delta^-(D)\) and the minimum and maximum out-degree are \(\delta^+=\delta^+(D)\) and \(\Delta^+=\Delta^+(D)\). If \(X\subseteq V(D)\), then \(D[X]\) is the subdigraph induced by \(X\). For an arc \((x,y)\in A(D)\), the vertex \(y\) is an out-neighbor of \(x\) and \(x\) is an in-neighbor of \(y\), and we also say that \(x\) dominates y or \(y\) is dominated by \(x\). For a real-valued function \(f: V(D)\rightarrow \mathbb{R}\), the weight of \(f\) is \(\omega(f)=\sum\limits_{v\in V(D)}f(v)\), and for \(S\subseteq V(D)\), we define \(f(S)=\sum\limits_{v\in S}f(v)\), hence \(\omega(f)=f(V(D))\). For notation and terminology not defined here, see [11, 12].
For an integer \(p\ge 1\), we define a set \(S\subseteq V(D)\) to be a \(p\)-dominating set of \(D\) if for all \(v\not\in S\), \(v\) is dominated by \(p\) vertices in \(S\). A 1-dominating set is also called a dominating set. The \(p\)–domination number \(\gamma_p(D)\) of a digraph \(D\) is the minimum cardinality of a \(p\)-dominating set of \(D\).
If \(k\ge 1\) is an integer, then the signed double Roman \(k\)-dominating function (SDR\(k\)DF) on a digraph \(D\) is a function \(f:V(D)\rightarrow\{-1,1,2,3\}\) satisfying the condition that \(\sum\limits_{x\in N^-[v]}f(x)\ge k\) for each \(v\in V(D)\), every vertex \(u\) with \(f(u)=-1\) has an in-neighbor \(z\) for which \(f(z)=3\) or two in-neighbors \(x\) and \(y\) with \(f(x)=f(y)=2\), and every vertex \(u\) with \(f(u)=1\) has an in-neighbor \(z\) with \(f(z)\ge 2\). The weight of an SDR\(k\)DF \(f\) is \(\omega(f)=\sum\limits_{v\in V(D)}f(v)\). The signed double Roman \(k\)-domination number \(\gamma_{sdR}^k(D)\) is the minimum weight of an SDR\(k\)DF on \(D\). A \(\gamma_{sdR}^k(D)\)-function is a signed double Roman \(k\)-domination function of weight \(\gamma_{sdR}^k(D)\).
An SDR\(k\)DF \(f\) on \(D\) can be represented by the ordered quadruple \((V_{-1},V_1,V_2,V_3)\) of \(V(D)\), where \(V_i=V_i(f)=\{v\in V(D):f(v)=i\}\) for \(i\in\{-1,1,2,3\}\). The signed double Roman \(k\)-domination number exists when \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\). Thus, we always assume that \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\). This condition guarantees that the constant function \(f(v) = 3\) satisfies \[{ f(N^-[v]) = 3(d^-(v) + 1) \ge k.}\]
In this paper, we initiate the study of the signed double Roman \(k\)-domination number of digraphs, and we present different sharp bounds on \(\gamma_{sdR}^k(D)\). In addition, we determine the signed double Roman \(k\)-domination number for certain classes of digraphs, including acyclic and circulant tournaments. Some of our results are extensions of well-known properties of the signed double Roman \(k\)-domination number \(\gamma_{sdR} ^k(G)\) of graphs \(G\).
While signed double Roman domination has been studied extensively for undirected graphs, its extension to digraphs is not merely an incremental generalization. In directed graphs, the condition for a vertex to be dominated depends on its in-neighborhood. This asymmetry captures phenomena that are inherently directed, such as information flow, hierarchical influence, or precedence constraints, which cannot be recovered by simply replacing each arc with an undirected edge and applying graph-theoretic results. For instance, in acyclic tournaments, circulant tournaments, and rooted trees, the directed parameter yields values that can differ significantly from those of their underlying undirected graphs. These examples demonstrate that the signed double Roman \(k\)-domination number is a genuinely new invariant for digraphs, not simply a reinterpretation of the known graph parameter.
The associated digraph \(D(G)\) of a graph \(G\) is the digraph obtained from \(G\) when each edge \(e\) of \(G\) is replaced by two oppositely oriented arcs with the same ends as \(e\). Since \(N^-_{D(G)}[v]=N_G[v]\) for each vertex \(v\in V(G)=V(D(G))\), the following useful observation is valid.
Observation 1.1. If \(D(G)\) is the associated digraph of a graph \(G\), then \(\gamma_{sdR}^k(D(G))=\gamma_{sdR}^k(G)\).
Let \(K_n\) and \(K_n^*\) be the complete graph and complete digraph of order \(n\), respectively. In [2, 4] and [13], the authors determine the signed double Roman \(k\)-domination number of complete graphs \(K_n\).
Proposition 1.2. [2, 4, 13] Let \(K_n\) be the complete graph with \(n\ge 2\) and \(n\ge\lceil k/3\rceil\). Then \(\gamma_{sdR}^k(K_n)=k\), with the exceptions \(k=1\) and \(n\in\{2,4\}\), or \(k=2\) and \(n=3\). In addition, \(\gamma_{sdR}^1(K_2)=\gamma_{sdR}^1(K_4)=2\) and \(\gamma_{sdR}^2(K_3)=3\).
Using Observation 1.1 and Proposition 1.2, we obtain the signed double Roman \(k\)-domination number of complete digraphs.
Corollary 1.3. Let \(K_n^*\) be the complete digraph with \(n\ge 2\) and \(n\ge\lceil k/3\rceil\). Then \(\gamma_{sdR}^k(K_n^*)=k\), with the exceptions \(k=1\) and \(n\in\{2,4\}\), or \(k=2\) and \(n=3\). In addition, \(\gamma_{sdR}^1(K_2^*)=\gamma_{sdR}^1(K_4^*)=2\) and \(\gamma_{sdR}^2(K_3^*)=3\).
Further direct consequences of known graph results will be given in the last paragraph of Section 4.
In this section, we present basic properties of the signed double Roman \(k\)-dominating function of digraphs.
Lemma 2.1. Let \(f=(V_{-1},V_1,V_2,V_3)\) be an SDR\(k\)DF on a digraph \(D\) of order \(n\) and minimum in-degree \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\). Then it holds:
Proof. Since (a), (b) and (c) are immediate, we only prove (d). If \(|V_{-1}|=0\), then \(V_1\cup V_2\cup V_3=V(D)\) is a \(\lceil\frac{k+1}{3}\rceil\)-dominating set of \(D\). Let now \(|V_{-1}|\ge 1\), and let \(v\in V_{-1}\) be an arbitrary vertex. Assume that \(v\) has \(j\) in-neighbors in \(V_1\), \(p\) in-neighbors in \(V_2\) and \(q\) in-neighbors in \(V_3\). The condition \(f(N^-[v])\ge k\) yields \(j+2p +3q-1\ge k\), and hence \(q\ge\frac{k+1-j-2p}{3}\). This implies \[j+p+q\ge j+p+\frac{k+1-j-2p}{3}=\frac{k+1+p+2j}{3}\ge\frac{k+1}{3}.\]
Therefore, \(v\) has at least \(j+p+q\ge\lceil\frac{k+1}{3}\rceil\) in-neighbors in \(V_1\cup V_2\cup V_3\). Since \(v\) was an arbitrary vertex in \(V_{-1}\), we deduce that \(V_1\cup V_2\cup V_3\) is a \(\lceil\frac{k+1}{3}\rceil\)-dominating set of \(D\). \(\square\)
Proposition 2.2. Assume that \(f=(V_{-1},V_1,V_2,V_3)\) is an SDR\(k\)DF on a digraph \(D\) of order \(n\) with \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\), and let \(\Delta^+=\Delta^+(D)\) and \(\delta^+=\delta^+(D)\). Then it holds:
Proof. (i) It follows from Lemma 2.1 (a) that \[\begin{aligned} k(|V_{-1}|+|V_1|+|V_2|+|V_3|) =& kn \; \le \sum\limits_{v\in V(D)}f(N^-[v])\;=\sum\limits_{v\in V(D)}(d_D^+(v)+1)f(v)\\ =& \sum\limits_{v\in V_3}3(d_D^+(v)+1)\;+\sum\limits_{v\in V_2}2(d_D^+(v)+1)\;+\sum\limits_{v\in V_1}(d_D^+(v)+1)\\ & -\sum\limits_{v\in V_{-1}}(d_D^+(v)+1)\\ \le & 3(\Delta^+\!+1)|V_3|\,+\,2(\Delta^+\!+1)|V_2|\,+\,(\Delta^+\!+1)|V_1|\\ & -\,(\delta^+\!+1)|V_{-1}|. \end{aligned}\]
This inequality chain yields the desired bound in (i).
(ii) Lemma 2.1 (a) implies \(|V_{-1}|=n-|V_1|-|V_2|-|V_3|\). Using this identity and Part (i), we arrive at (ii).
(iii) According to Lemma 2.1 and Part (ii), we obtain Part (iii) as follows: \[\begin{aligned} (\Delta^++\delta^++2)\omega(f) =& (\Delta^++\delta^++2) (|V_1|+2|V_2|+3|V_3|-|V_{-1}|)\\ =& (\Delta^++\delta^++2)(2|V_1|+3|V_2|+4|V_3|-n)\\ \ge & 2(\delta^++k+1)n \,-\, 2(3\Delta^++\delta^++4)|V_3| \,-\, 2(2\Delta^++\delta^++3)|V_2|\\ & +\,(\Delta^++\delta^++2)(3|V_2|+4|V_3|-n)\\ =& (\delta^+-\Delta^++2k)n \,+\, (\delta^+-\Delta^+)|V_2| \,+\, 2(\delta^+-\Delta^+)|V_3|. \end{aligned}\]
(iv) The inequality chain in the proof of Part (i) and Lemma 2.1 (a) show that \[\begin{aligned} kn \le & 3(\Delta^++1)|V_3| \,+\, 2(\Delta^++1)|V_2| \,+\, (\Delta^++1)|V_1| \,-\,(\delta^++1)|V_{-1}|\\ \le & 3(\Delta^++1)|V_1\cup V_2\cup V_3|\,-\,(\delta^++1)|V_{-1}|\\ =& 3(\Delta^++1)|V_1\cup V_2\cup V_3|\,-\,(\delta^++1)(n-|V_1\cup V_2\cup V_3|)\\ =& (3\Delta^++\delta^++4)|V_1\cup V_2\cup V_3|\,-\,(\delta^++1)n, \end{aligned}\] and thus \[|V_1\cup V_2\cup V_3|\,\ge\,\frac{n(\delta^++k+1)}{3\Delta^++\delta^++4}.\]
Using this inequality and Lemma 2.1, we obtain \[\begin{aligned} \omega(f) =& 2|V_1\cup V_2\cup V_3|-n+|V_2|+2|V_3|\\ \ge & \frac{n(\delta^+-3\Delta^++2k-2)}{3\Delta^++\delta^++4}+|V_2|+2|V_3|. \end{aligned}\]
This is the bound in Part (iv), and the proof is complete. \(\square\)
We start with a general upper bound, and we characterize all extremal digraphs.
Theorem 3.1. Let \(k\ge 1\) be an integer, and let \(D\) be a digraph of order \(n\) with \(\delta^-(D)\ge\lceil \frac{k}{3}\rceil-1\). Then \(\gamma_{sdR}^k(D)\le 3n\), with equality if and only if \(k=3t\) for an integer \(t\ge 1\), \(\delta^-(D)=\frac{k}{3}-1\), and each vertex of \(D\) is of minimum in-degree or has an out-neighbor of minimum in-degree.
Proof. Define the function \(g:V(D)\rightarrow\{-1,1,2,3\}\) by \(g(x)=3\) for each vertex \(x\in V(D)\). Since \(\delta^-(D)\ge\lceil \frac{k}{3}\rceil-1\), the function \(g\) is an SDR\(k\)DF on \(D\) of weight \(3n\) and thus \(\gamma_{sdR}^k(D)\le 3n\).
Now, let \(k=3t\) for an integer \(t\ge 1\), \(\delta^-(D)=\frac{k}{3}-1\), and assume that each vertex of \(D\) is of minimum in-degree or has an out-neighbor of minimum in-degree. Let \(f\) be a \(\gamma_{sdR}^k(D)\)-function, and let \(x\in V(D)\) be an arbitrary vertex. If \(d^-(x)=\frac{k}{3}-1\), then \(f(N^-[x])\ge k\) implies \(f(x)=3\). If \(x\) is not of minimum in-degree, then \(x\) has an out-neighbor \(w\) of minimum in-degree. Now, the condition \(f(N^-[w])\ge k\) implies \(f(x)=3\). Thus, \(f(x)=3\) for each vertex \(x\in V(D)\), and we obtain \(\gamma_{sdR}^k(D)=3n\) in this case.
Conversely, assume that \(\gamma_{sdR}^k(D)=3n\). If \(k=3t+\epsilon\) for an integer \(t\ge 0\) and \(\epsilon\in\{1,2\}\), then \(\delta^-(D)\ge t\). Define the function \(h:V(D)\rightarrow\{-1,1,2,3\}\) by \(h(w)=2\) for an arbitrary vertex \(w\) and \(h(x)=3\) for each vertex \(x\in V(D)\setminus\{w\}\). Then \[h(N^-[v])\;=\sum\limits_{x\in N^-[v]} { h(x)} \ge 3t+2\ge k,\] for each \(v\in V(D)\). Thus, the function \(h\) is an SDR\(k\)DF on \(D\) of weight \(3n-1\), a contradiction to the assumption \(\gamma_{sdR}^k(D)=3n\).
Let now \(k=3t\) for an integer \(t\ge 1\) and assume that there exists a vertex \(w\) such that \(d^-(w)\ge t\) and \(d^-(x)\ge t\) for each out-neighbor of \(w\). Define the function \(h_1:V(D)\rightarrow\{-1,1,2,3\}\) by \(h_1(w)=2\) and \(h_1(x)=3\) for each vertex \(x\in V(D)\setminus\{w\}\). Then \(h_1(N^-[w])\ge 3t+2=k+2\), \(h_1(N^-[x])\ge 3t+2=k+2\) for each vertex \(x\in N^+(w)\) and \(h_1(N^-[y])\ge k\) for each vertex \(y\not\in N^+[w]\). Hence the function \(h_1\) is an SDR\(k\)DF on \(D\) of weight \(3n-1\), and we obtain the contradiction \(\gamma_{sdR}^k(D)\le 3n-1\). This completes the proof. \(\square\)
Proposition 3.2. If \(D\) is a digraph of order \(n\) with minimum in-degree \(\delta^-\ge \lceil \frac{k}{2}\rceil-1\), then \(\gamma_{sdR}^k(D)\le 2n\).
Proof. Define the function \(f:V(D)\rightarrow\{-1,1,2,3\}\) by \(f(x)=2\) for each vertex \(x\in V(D)\). Since \(\delta^-\ge \lceil \frac{k}{2}\rceil-1\), the function \(f\) is an SDR\(k\)DF on \(D\) of weight \(2n\) and thus \(\gamma_{sdR}^k(D)\le 2n\). \(\square\)
Theorem 3.3. If \(D\) is a digraph of order \(n\ge 2\) and minimum in-degree \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\), then \[\gamma_{sdR}^k(D)\ge\min\{\gamma_{\lceil\frac{k+1}{3}\rceil}(D)+1; \; 2\gamma_{\lceil\frac{k+1}{3}\rceil}(D)+2-n\}.\]
Proof. Let \(f=(V_{-1},V_1,V_2,V_3)\) be a \(\gamma_{sdR}^k(D)\)-function. If \(|V_{-1}|=|V_1|=0\), then it follows from Lemma 2.1 that \[\gamma_{sdR}^k(D) = 2|V_2|+3|V_3|\ge 2|V_2\cup V_3|\ge 2\gamma_{\lceil\frac{k+1}{3}\rceil}(D)\ge 2\gamma_{\lceil\frac{k+1}{3}\rceil}(D)+2-n.\]
If \(|V_{-1}|=0\) and \(|V_1|\ge 1\), then \(|V_2|+|V_3|\ge 1\), and Lemma 2.1 implies that \[\gamma_{sdR}^k(D) = |V_1|+2|V_2|+3|V_3|=|V_1\cup V_2\cup V_3| +|V_2|+2|V_3|\ge \gamma_{\lceil\frac{k+1}{3}\rceil}(D)+1.\]
Now, let \(|V_{-1}|\ge 1\). Then \(|V_2|+2|V_3|\ge 2\), and we deduce from Lemma 2.1 that \[\begin{aligned} \gamma_{sdR}^k(D) =& |V_1|+2|V_2|+3|V_3|-|V_{-1}|=2|V_1|+3|V_2|+4|V_3|-n\\ =& 2|V_1\cup V_2\cup V_3|+|V_2|+2|V_3|-n \ge 2|V_1\cup V_2\cup V_3|+2-n\\ \ge & 2\gamma_{\lceil\frac{k+1}{3}\rceil}(D)+2-n. \end{aligned}\]
This completes the proof. \(\square\)
The next two examples will demonstrate that Theorem 3.3 is sharp for \(k=3\) and \(k=2\).
Example 3.4. Let \(n\ge 2\) be an integer, and assume that \(H\) is the digraph with vertex set \(\{w, z_1,z_2,\ldots,z_{n-1}\}\) and arc set consisting of \((z_1,w)\) and \((w,z_i)\) for \(1\le i\le n-1\). Define a function \(f\) by \(f(w)=2\) and \(f(z_i)=1\) for \(1\le i\le n-1\), so that \(\omega(f)=n+1\). Then \(f\) is a \(\gamma_{sdR}^3(H)\)-function because \(f(N^-[w]) = f(N^-[z_i]) = 3\) and every vertex of weight \(1\) has an in-neighbor of weight \(2\). Moreover, no vertex is dominated by other two vertices, and so \(\gamma_{\lceil\frac{3+1}{3}\rceil}(H)=\gamma_{2}(H)=n\). Thus, \(\gamma^3_{sdR}(H)=\gamma_{\lceil\frac{3+1}{3}\rceil}(H)+1,\) and hence equality holds in Theorem 3.3 for \(k=3\).
Example 3.5. Let \(n\ge 2\) be an integer, and assume that \(F\) is the digraph with vertex set \(\{w, z_1,z_2,\ldots,z_{n-1}\}\) and arc set \(\{(w,z_i)\; | \; 1\le i\le n-1\}\). Define a function \(f\) by \(f(w)=3\) and \(f(z_i)=-1\) for \(1\le i\le n-1\), so that \(\omega(f)=4-n\). Then \(f\) is a \(\gamma_{sdR}^2(F)\)-function because \(f(N^-[w]) \ge 2\), \(f(N^-[z_i]) = 2\), and each vertex assigned \(-1\) has an in-neighbor assigned \(3\). Moreover, \(w\) is a dominating vertex, and so \(\gamma_{\lceil\frac{2+1}{3}\rceil}(F)=\gamma_{1}(F)=1\). Hence, \(\gamma^2_{sdR}(F)=2\gamma_{\lceil\frac{2+1}{3}\rceil}(F)+2-n=4-n,\) and therefore equality holds in Theorem 3.3 for \(k=2\).
In a particular case, we considerably improve Theorem 3.3.
Proposition 3.6. Let \(D\) be a digraph of order \(n\ge 2\) and minimum in-degree \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\). If there exists a \(\gamma_{sdR}^k(D)\)-function \(f=(V_{-1},V_1,V_2,V_3)\) with \(|V_{1}|=|V_2|=0\), then \[\gamma_{sdR}^k(D) \,\ge\, 4\gamma_{\lceil\frac{k+1}{3}\rceil}(D)-n.\]
Proof. As in the proof of Theorem 3.3, we obtain \[\begin{aligned} \gamma_{sdR}^k(D) =& |V_1|+2|V_2|+3|V_3|-|V_{-1}|=2|V_1|+3|V_2|+4|V_3|-n\\ =& 4|V_3|-n \ge 4\gamma_{\lceil\frac{k+1}{3}\rceil}(D)-n. \end{aligned}\] \(\square\)
A digraph \(D\) is \(r\)–out-regular if \(\Delta^+(D)=\delta^+(D)=r\) and \(r\)–regular if \(\Delta^+(D)=\Delta^-(D)=\delta^+(D)=\delta^-(D)=r\). As an application of Proposition 2.2 (iii), we obtain a lower bound on the signed double Roman \(k\)-domination number for \(r\)-out-regular digraphs.
Corollary 3.7. If \(D\) is an \(r\)-out-regular digraph of order \(n\) with \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\), then \[\gamma_{sdR}^k(D)\ge\left\lceil\frac{kn}{r+1}\right\rceil.\]
Using Corollary 3.7 and Observation 1.1, we obtain the next known result.
Corollary 3.8. [4] If \(G\) is an \(r\)-regular graph of order \(n\) with \(r\ge \lceil \frac{k}{3}\rceil-1\), then \[\gamma_{sdR}^k(G)\ge\left\lceil\frac{kn}{r+1}\right\rceil.\]
Example 3.9. Let \(k\ge 2\) be an even integer. If \(H\) is a \((k/2-1)\)-regular digraph of order \(n\), then it follows from Corollary 3.7 that \(\gamma_{sdR}^k(H)\ge 2n\), and hence \(\gamma_{sdR}^k(H)=2n\) according to Proposition 3.2.
Example 3.9 demonstrates that Proposition 3.2 and Corollary 3.7 are both sharp.
If \(D\) is not out-regular, then the next lower bound on the signed double Roman \(k\)-domination number holds.
Corollary 3.10. Let \(D\) be a digraph of order \(n\), minimum in-degree \(\delta^- \!\ge \lceil \frac{k}{3}\rceil-1\), minimum out-degree \(\delta^+\) and maximum out-degree \(\Delta^+\). If \(\delta^+\!<\Delta^+\), then \[\gamma_{sdR}^k(D)\ge\left(\frac{-3\Delta^++3\delta^++4k}{3\Delta^++\delta^++4}\right)n.\]
Proof. Multiplying both sides of the inequality in Proposition 2.2 (iv) by \(\Delta^+-\delta^+\) and adding the resulting inequality to the inequality in Proposition 2.2 (iii), we obtain the desired lower bound. \(\square\)
Since \(\Delta^+(D(G))= \Delta(G)\) and \(\delta^+(D(G))=\delta(G)\), Corollary 3.10 and Observation 1.1 imply the next known result.
Corollary 3.11. [4, 13] Let \(G\) be a graph of order \(n\), minimum degree \(\delta\ge \lceil \frac{k}{3}\rceil-1\) and maximum degree \(\Delta\). If \(\delta<\Delta\), then \[\gamma_{sdR}^k(G)\ge \left(\frac{-3\Delta+3\delta+4k}{3\Delta+\delta+4}\right)n.\]
In [13], the authors present for each integer \(k\ge 1\) an infinite family of graphs with equality in the bound of Corollary 3.11. Using these examples and Observation 1.1, we obtain for each integer \(k\ge 1\) an infinite family of digraphs with equality in the bound of Corollary 3.10. Therefore, the inequality in Corollary 3.10 is sharp for each \(k\ge 1\).
In addition, using Examples 1–5 in [13] and Observation 1.1, we conclude that the bound in Proposition 3.6 is also sharp for every integer \(k\ge 1\).
A tournament is a digraph \(D\) in which for every pair \(u,v\) of different vertices, either \((u,v)\in A(D)\) or \((v,u)\in A(D)\), but not both. An acyclic tournament \({\rm AT}(n)\) of order \(n\) is a tournament with vertex set \(V({\rm AT}(n))=\{u_1,u_2,\ldots,u_n\}\) such that an arc goes from \(u_i\) into \(u_j\) if and only if \(i<j\).
Theorem 4.1. Let \({\rm AT}(n)\) be an acyclic tournament of order \(n\ge 5\). Then \(\gamma_{sdR}^k({\rm AT}(n))=k\) for \(1\le k\le 3\).
Proof. Let \(f\) be a \(\gamma_{sdR}^k({\rm AT}(n))\)-function for \(1\le k\le 3\). Since \(V({\rm AT}(n))=N^-[u_n]\), we observe that \[\gamma_{sdR}^k({\rm AT}(n))=\omega(f)=f(V({\rm AT}(n)))=f(N^-[u_n])\ge k.\]
Assume first that \(k=1\). If \(n=2t\) is even for an integer \(t\ge 3\), then define \(g\) by \(g(u_1)=3\), \(g(u_2)=2\), \(g(u_3)=g(u_4)=\ldots=g(u_{t-1})=1\) and \(g(u_t)=g(u_{t+1})=\ldots=g(u_{2t})=-1\). If \(n=2t+1\) is odd for an integer \(t\ge 2\), then define \(g\) by \(g(u_1)=3\), \(g(u_2)=g(u_3)=\ldots=g(u_{t})=1\) and \(g(u_{t+1})=g(u_{t+2})=\ldots=g(u_{2t+1})=-1\). In both cases \(g\) is an SDR1DF on \({\rm AT}(n)\) of weight \(\omega(g)=1\). Hence \(\gamma_{sdR}^1({\rm AT}(n))\le 1\) and thus \(\gamma_{sdR}^1({\rm AT}(n))=1\).
Assume second that \(k=2\). If \(n=2t\) is even for an integer \(t\ge 3\), then define \(g\) by \(g(u_1)=3\), \(g(u_2)=g(u_3)=\ldots=g(u_{t})=1\) and \(g(u_{t+1})=g(u_{t+2})=\ldots=g(u_{2t})=-1\). If \(n=5\), then define \(g\) by \(g(u_1)=3\), \(g(u_2)=2\) and \(g(u_3)=g(u_4)=g(u_5)=-1\). If \(n=2t+1\) is odd for an integer \(t\ge 3\), then define \(g\) by \(g(u_1)=3\), \(g(u_2)=2\), \(g(u_3)=g(u_4)=\ldots=g(u_{t})=1\) and \(g(u_{t+1})=g(u_{t+2})=\ldots=g(u_{2t+1})=-1\). In all cases \(g\) is an SDR2DF on \({\rm AT}(n)\) of weight \(\omega(g)=2\). This shows that \(\gamma_{sdR}^2({\rm AT}(n))=2\).
Finally, assume that \(k=3\). If \(n=2t\) is even for an integer \(t\ge 3\), then define \(g\) by \(g(u_1)=3\), \(g(u_2)=2\), \(g(u_3)=g(u_4)=\ldots=g(u_{t})=1\) and \(g(u_{t+1})=g(u_{t+2})=\ldots=g(u_{2t})=-1\). If \(n=5\), then define \(g\) by \(g(u_1)=g(u_2)=3\) and \(g(u_3)=g(u_4)=g(u_5)=-1\). If \(n=2t+1\) is odd for an integer \(t\ge 3\), then define \(g\) by \(g(u_1)=g(u_2)=3\), \(g(u_3)=g(u_4)=\ldots=g(u_{t})=1\) and \(g(u_{t+1})=g(u_{t+2})=\ldots=g(u_{2t+1})=-1\). In all cases \(g\) is an SDR3DF on \({\rm AT}(n)\) of weight \(\omega(g)=3\) and therefore \(\gamma_{sdR}^3({\rm AT}(n))=3\). \(\square\)
For completeness, we note that \(\gamma_{sdR}^1({\rm AT}(3))=1\), \(\gamma_{sdR}^1({\rm AT}(4))=2\), \(\gamma_{sdR}^2({\rm AT}(3))=3\), \(\gamma_{sdR}^2({\rm AT}(4))=2\) and \(\gamma_{sdR}^3({\rm AT}(3))=\gamma_{sdR}^3({\rm AT}(4))=3\).
Let \(n=2r+1\ge 3\), where \(r\ge 1\) is an integer. We define the circulant tournament \({\rm CT}(n)\) of order \(n\) as follows. If \(V({\rm CT}(n))=\{u_0,u_1,\ldots,u_{n-1}\}\) is the vertex set of \({\rm}CT(n)\), then for each \(i\), the arcs are going from \(u_i\) to the vertices \(u_{i+1},u_{i+2},\ldots,u_{i+r}\), where the indices are taken modulo \(n\).
Theorem 4.2. Let \({\rm CT}(n)\) be a circulant tournament of order \(n=2r+1\) where \(r\ge 4\) is an integer, and let \(k\ge 1\) be an integer such that \(2k\le 3n+3\).
Proof. Let \(f\) be a \(\gamma_{sdR}^k({\rm CT}(n))\)-function. If \(f(x)=3\) for each vertex \(x\), then \(\omega(f)=3n\), and if \(f(x)\ge 2\) for each vertex \(x\), then \(\omega(f)\ge 2n\). In addition, if \(f(x)\ge 1\) for each vertex \(x\), then \(\omega(f)\ge n+2,\) since the minimum weight is attained when two vertices \(u_i\) and \(u_{i+r}\) have weight \(2\), while all remaining vertices have weight \(1\). Now, we assume without loss of generality that \(f(u_0)=-1\). Since \(f(N^-[u_0])\ge k\) and \(f(N^-[u_r])\ge k\), we deduce that \[\omega(f)=f(V({\rm CT}(n)))=f(N^-[u_0])+f(N^-[u_r])-f(u_0)\ge 2k+1.\]
(a) If \(2k\le n+1\), then the observations above imply that \(\gamma_{sdR}^k({\rm CT}(n))\ge 2k+1\).
To prove the converse inequality, we distinguish two cases.
Case 1. Assume that \(r=2t\) is even for some integer \(t\ge 2\). If \(k=2s+1\) for some integer \(s\) where \(0\le s\le t\), then define the function \(g\) by \(g(u_0)=g(u_{2t+1})=3\), \(g(u_1)=g(u_2)=\ldots=g(u_{t+s-1})=1\), \(g(u_{2t+2})=g(u_{2t+3})=\ldots=g(u_{3t+s})=1\) and \(g(x)=-1\) otherwise. Then \(g\) is an SDR\(k\)DF on \({\rm CT}(n)\) of weight \(6+2(t+s-1)-(2t-2s+1)=4s+3=2k+1\). If \(k=2s\) for some integer \(s\) (\(1\le s\le t\)), then define the function \(g\) by \(g(u_0)=g(u_{2t+1})=3\), \(g(u_1)=g(u_{2t+2})=2\), \(g(u_2)=g(u_3)=\ldots=g(u_{t+s-2})=1\), \(g(u_{2t+3})=g(u_{2t+4})=\ldots=g(u_{3t+s-1})=1\) and \(g(x)=-1\) otherwise. Then \(g\) is an SDR\(k\)DF on \({\rm CT}(n)\) of weight \(10+2(t+s-3)-(2t-2s+3)=4s+1=2k+1\). This shows that \(\gamma_{sdR}^k({\rm CT}(n))=2k+1\) in this case.
Case 2. Assume that \(r=2t+1\) is odd for some integer \(t\ge 2\). If \(k=2s+1\) for some integer \(s\) where \(0\le s\le t\), then define the function \(g\) by \(g(u_0)=g(u_{2t+2})=3\), \(g(u_1)=g(u_{2t+3})=2\), \(g(u_2)=g(u_3)=\ldots=g(u_{t+s-1})=1\), \(g(u_{2t+4})=g(u_{2t+5})=\ldots=g(u_{3t+s+1})=1\) and \(g(x)=-1\) otherwise. Then \(g\) is an SDR\(k\)DF on \({\rm CT}(n)\) of weight \(10+2(t+s-2)-(2t-2s+3)=4s+3=2k+1\). If \(k=2s\) for some integer \(s\) (\(1\le s\le t\)), then define the function \(g\) by \(g(u_0)=g(u_{2t+2})=3\), \(g(u_1)=g(u_2)=\ldots=g(u_{t+s-1})=1\), \(g(u_{2t+3})=g(u_{2t+4})=\ldots=g(u_{3t+s+1})=1\) and \(g(x)=-1\) otherwise. Then \(g\) is an SDR\(k\)DF on \({\rm CT}(n)\) of weight \(6+2(t+s-1)-(2t-2s+3)=4s+1=2k+1\), and hence \(\gamma_{sdR}^k({\rm CT}(n))=2k+1\) also when \(r\) is odd.
(b) If \(n+2\le 2k\le 2n\), then the observations above show that \(\gamma_{sdR}^k({\rm CT}(n))\ge 2k-1\) if \(f(x)\ge 2\) for each vertex \(x\), or if there exists a vertex \(y\) with \(f(y)=-1\). If, without loss of generality, \(f(u_0)=1\), then \[\omega(f)=f(V({\rm CT}(n)))=f(N^-[u_0])+f(N^-[u_r])-f(u_0)\ge 2k-1.\]
Consequently, \(\gamma_{sdR}^k({\rm CT}(n))\ge 2k-1\) in each case. For the converse inequality, let \(k=r+s\) for an integer \(s\) such that \(2\le s\le r+1\). Define the function \(g\) by \(g(u_0)=g(u_1)=\ldots=g(u_{s-2})=2\), \(g(u_{s-1})=g(u_{s})=\ldots=g(u_{r})=1\), \(g(u_{r+1})=g(u_{r+2})=\ldots=g(u_{r+s-1})=2\) and \(g(u_{r+s})=g(u_{r+s+1})=\ldots=g(u_{2r})=1\). Then \(g\) is an SDR\(k\)DF on \({\rm CT}(n)\) of weight \(2(s-1)+r-s+2+2(s-1)+r-s+1=2r+2s-1=2k-1\) and thus \(\gamma_{sdR}^k({\rm CT}(n))=2k-1\).
(c) If \(2k=2n+2\), then we have seen above that \(\gamma_{sdR}^k({\rm CT}(n))\ge 2k-2\). Conversely, define \(g\) by \(g(x)=2\) for each vertex \(x\). Then \(g\) is an SDR\(k\)DF on \({\rm CT}(n)\) of weight \(2n=2k-2\), and hence \(\gamma_{sdR}^k({\rm CT}(n))=2k-2\).
(d) If \(2n+3\le 2k\le 3n+1\), then the observations above imply that \(\gamma_{sdR}^k({\rm CT}(n))\ge 2k-2\) in the case that \(f(x)\ge 3\) for every vertex \(x\), or that there exists a vertex \(y\) with \(f(y)\le 1\). If, without loss of generality, \(f(u_0)=2\), then \[\omega(f)=f(V({\rm CT}(n)))=f(N^-[u_0])+f(N^-[u_r])-f(u_0)\ge 2k-2.\]
Hence \(\gamma_{sdR}^k({\rm CT}(n))\ge 2k-2\) in each case. For the converse inequality, let \(k=2r+s\) for an integer \(s\) such that \(3\le s\le r+2\). Define the function \(g\) by \(g(u_0)=g(u_1)=\ldots=g(u_{s-3})=3\), \(g(u_{s-2})=g(u_{s-1})=\ldots=g(u_{r})=2\), \(g(u_{r+1})=g(u_{r+2})=\ldots=g(u_{r+s-2})=3\) and \(g(u_{r+s-1})=g(u_{r+s})=\ldots=g(u_{2r})=2\). Then \(g\) is an SDR\(k\)DF on \({\rm CT}(n)\) of weight \(3(s-2)+2(r-s+3)+3(s-2)+2(r-s+2)=4r+2s-2=2k-2\) and thus \(\gamma_{sdR}^k({\rm CT}(n))=2k-2\).
(e) Assume that \(2k=3n+3\). We have seen above that \(\gamma_{sdR}^k({\rm CT}(n))\ge 2k-3\) in every case. Conversely, the function \(g\) with \(g(x)=3\) for each vertex \(x\) leads to \(\gamma_{sdR}^k({\rm CT}(n))=2k-3\) in the last case. \(\square\)
If \(C_n\) is an oriented cycle of order \(n\ge 3\), then we next determine \(\gamma_{sdR}^k(C_n)\) for \(1\le k\le 6\).
Example 4.3. If \(n\ge 3\) is an integer, then it holds:
Proof. Denote \(C_n=v_0v_1\ldots v_{n-1}v_0.\)
(a) Let \(f\) be a \(\gamma_{sdR}^1(C_n)\)-function. If \(f(v_i)\ge 1\) for all \(0\le i\le n-1\), then \(f(v_j)\ge 2\) for at least one index \(j\) and therefore \(\omega(f)\ge n+1\). If \(f(v_i)=-1\) for an index \(i\) such that \(0\le i\le n-1\), then the definition leads to \(f(v_{i-1})=3\), where the indices are taken modulo \(n\). These observations show that \(\omega(f)\ge n\) when \(n\) is even and \(\omega(f)\ge n+1\) when \(n\) is odd.
Conversely, if \(n=2t\) is even, then define the function \(g:V(C_{2t})\rightarrow\{-1,1,2,3\}\) by \(g(v_{2i})=3\) and \(g(v_{2i+1})=-1\) for \(0\le i\le t-1\). Then \(g\) is an SDR1DF on \(C_{2t}\) of weight \(\omega(g)=2t=n\). Thus, \(\gamma_{sdR}^1(C_n)\le n\). Consequently, \(\gamma_{sdR}^1(C_n)=n\) in this case. If \(n=2t+1\) is odd, then define \(g:V(C_{2t+1})\rightarrow\{-1,1,2,3\}\) by \(g(v_{2i})=3\), \(g(v_{2i+1})=-1\) for \(0\le i\le t-1\) and \(g(v_{2t})=2\). Then \(g\) is an SDR1DF on \(C_{2t+1}\) of weight \(\omega(g)=2t+2=n+1\). This implies that \(\gamma_{sdR}^1(C_n)=n+1\) when \(n\) is odd.
(b) Let \(f\) be a \(\gamma_{sdR}^2(C_n)\)-function. If \(f(v_i)\ge 1\) for all \(0\le i\le n-1\), then \(f(v_j)\ge 2\) for at least one index \(j\) and therefore \(\omega(f)\ge n+1\). If in addition, \(n\ge 3\) is odd, then there are at least two different indices \(p\) and \(q\) with \(f(v_p),f(v_q)\ge 2\) and hence \(\omega(f)\ge n+2\) in this case. If \(f(v_i)=-1\), then the definition leads to \(f(v_{i-1})=3\), where the indices are taken modulo \(n\). These observations show that \(\omega(f)\ge n\) when \(n\) is even.
Conversely, if \(n=2t\) is even, then define \(g:V(C_{2t})\rightarrow\{-1,1,2,3\}\) as in case (a), and we obtain \(\gamma_{sdR}^2(C_n)=n\).
Let now \(n=2t+1\) be odd. If \(f(v_i)\ge 1\) for all \(0\le i\le n-1\), then we have seen above that \(\omega(f)\ge n+2\). In addition, the definitions yield \(f(v_i)+f(v_{i+1})\ge 2\), and if \(f(v_i)=-1\) then \(f(v_{i-1})=f(v_{i+1})=3\), where the indices are taken modulo \(n\). If we assume without loss of generality that \(f(v_1)=-1\), then we deduce that \[\omega(f)\ge f(v_0)+f(v_1)+f(v_2)+\sum\limits_{i=3}^{2t}f(v_i)\ge 5+(n-3)=n+2.\]
Therefore, \(\omega(f)\ge n+2\) in each case when \(n\) is odd. Now, define \(g:V(C_{2t+1})\rightarrow\{-1,1,2,3\}\) by \(g(v_{2i})=3\), \(g(v_{2i+1})=-1\) for \(0\le i\le t-1\) and \(g(v_{2t})=3\). Then \(g\) is an SDR2DF on \(C_{2t+1}\) of weight \(\omega(g)=2t+3=n+2\). Hence \(\gamma_{sdR}^2(C_n)=n+2\) when \(n\) is odd.
(c) Let now \(3\le k\le 6\). Corollary 3.7 implies \(\gamma_{sdR}^k(C_n)\ge \left\lceil\frac{kn}{2}\right\rceil\).
If \(k=3\) and \(n=2t\) is even, then define the function \(g:V(C_{2t})\rightarrow\{-1,1,2,3\}\) by \(g(v_{2i})=1\) and \(g(v_{2i+1})=2\) for \(0\le i\le t-1\). If \(k=3\) and \(n=2t+1\) is odd, then define the function \(g:V(C_{2t+1})\rightarrow\{-1,1,2,3\}\) by \(g(v_{2i})=1\), \(g(v_{2i+1})=2\) for \(0\le i\le t-1\) and \(g(v_{2t})=2\). In both cases \(g\) is an SDR3DF on \(C_{n}\) of weight \(\omega(g)=\lceil\frac{3n}{2}\rceil\). This leads to \(\gamma_{sdR}^3(C_n)=\left\lceil\frac{3n}{2}\right\rceil\).
If \(k=4\), then define the function \(g\) with \(g(v_{i})=2\) for \(0\le i\le n-1\). Consequently, \(\gamma_{sdR}^4(C_n)=2n=\left\lceil\frac{4n}{2}\right\rceil\).
If \(k=5\) and \(n=2t\) is even, then define the function \(g:V(C_{2t})\rightarrow\{-1,1,2,3\}\) by \(g(v_{2i})=2\) and \(g(v_{2i+1})=3\) for \(0\le i\le t-1\). If \(k=5\) and \(n=2t+1\) is odd, then define the function \(g:V(C_{2t+1})\rightarrow\{-1,1,2,3\}\) by \(g(v_{2i})=2\), \(g(v_{2i+1})=3\) for \(0\le i\le t-1\) and \(g(v_{2t})=3\). In both cases \(g\) is an SDR5DF on \(C_{n}\) of weight \(\omega(g)=\lceil\frac{5n}{2}\rceil\), and we obtain the desired result.
If \(k=6\), then the function \(g\) with \(g(v_{i})=3\) for \(0\le i\le n-1\) leads to the desired identity. \(\square\)
Let \(K_{p,q}^*\) be the complete bipartite digraph with partite sets of cardinalities \(p\) and \(q\), and let \(C_n^*\) be the associated digraph of a cycle of length \(n\). Using Observation 1.1, Proposition 4.2 in [2] and Proposition 8 in [13], one can determine \(\gamma_{sdR}^k(C_n^*)\) for \(1\le k\le 9\). Applying Observation 1.1 and Proposition 4.3 in [2], we obtain \(\gamma_{sdR}^1(K_{p,q}^*)\) for \(2\le p\le q\). In addition, Observation 1.1 and Proposition 11 in [13] lead to \(\gamma_{sdR}^k(K_{p,p}^*)\) for \(2\le k\le 3p+3\).
In this section, we continue to study lower bounds for the signed double Roman \(k\)-domination number \(\gamma_{sdR}^k(D)\).
Theorem 5.1. If \(D\) is a digraph of order \(n\) with \(\delta^-(D)\ge \lceil \frac{k}{3}\rceil-1\), then \[\gamma_{sdR}^k(D)\ge k+1+\Delta^-(D)-n.\]
Proof. Let \(w\in V(D)\) be a vertex of maximum in-degree, let \(f\) be a \(\gamma_{sdR}^k(D)\)-function, and denote \(Y=V(D)\setminus N^-[w]\). Then the definitions imply \[\begin{aligned} \gamma_{sdR}^k(D) =& \sum\limits_{x\in V(D)}f(x)\;\;=\sum\limits_{x\in N^-[w]}f(x)\;+\;\sum\limits_{x\in Y} f(x)\\ \ge & k+\sum\limits_{x\in Y} f(x)\;\ge\; -(n-(\Delta^-(D)+1))\\ =& k+1+\Delta^-(D)-n, \end{aligned}\] and the proof of the desired lower bound is complete. \(\square\)
It follows from Corollary 1.3 that \(\gamma_{sdR}^k(K_n^*)=k\), with the exceptions \(k=1\) and \(n\in\{2,4\}\), or \(k=2\) and \(n=3\). Therefore, the bound given in Theorem 5.1 is sharp.
Let \(S_1\) be an orientation of the star \(K_{1,n-1}\) such that the center \(w\) has out-degree \(n-1\), and let \(S_2\) consists of \(S_1\) together with an arc \(vw\) for an arbitrary leaf \(v\) of \(K_{1,n-1}\). In addition, let \(S^2_n\) be the family of digraphs \(H\) with \(\Delta^-(H)\le 2\) such that \(H\) contains a spanning subdigraph \(S_1\).
Theorem 5.2. Let \(D\) be a digraph of order \(n\ge 2\). Then \(\gamma_{sdR}^1(D)\ge 4-n\), with equality if and only if \(D\in {S^2_n}\).
Proof. If \(\Delta^-(D)=0\), then \(\gamma_{sdR}^1(D)=2n>4-n\). If \(\Delta^-(D)\ge 1\), then Theorem 5.1 implies \(\gamma_{sdR}^1(D)\ge 3-n\), However, if \(\gamma_{sdR}^1(D)=3-n\), then there exists exactly one vertex of weight 2 and \(n-1\) vertices of weight \(-1\). Since this is impossible, we obtain the desired lower bound.
If \(D\in{S^2_n}\), then we define the function \(g\) as follows: \(g(w)=3\) and \(g(x)=-1\) for all \(x\not= w\). Since \(\Delta^-(D)\le 2\), we have \(g(N^-[y])\ge 1\) for any vertex \(y\) in \(D\). Also, every vertex of weight \(-1\) has an in-neighbor of weight 3. Thus, this function is an SDR1DF on \(D\). Therefore, \(\gamma_{sdR}^1(D)\le 4-n\) and hence \(\gamma_{sdR}^1(D)=4-n\) for \(D\in{S^2_n}\).
Assume now that \(\gamma_{sdR}^1(D)=4-n\), and let \(f\) be a \(\gamma_{sdR}^1(D)\)-function. This implies that \(D\) has exactly one vertex \(u\) with \(f(u)=3\) and \(n-1\) vertices \(x_1,x_2,\ldots,x_{n-1}\) such that \(f(x_i)=-1\) for \(1\le i\le n-1\). It follows that \((u,x_i)\in A(D)\) for all \(1\le i\le n-1\). Since \(f\) is a \(\gamma_{sdR}^1(D)\)-function, we have \(g(N^-[y])\ge 1\) for any vertex \(y\) in \(D\). Therefore, \(\Delta^-(D)\le 2\) and hence \(D\in {S^2_n}\). \(\square\)
Theorem 5.3. Let \(D\) be a digraph of order \(n\ge 2\). Then \(\gamma_{sdR}^2(D)\ge 4-n\), with equality if and only if \(D=S_1\) or \(D=S_2\).
Proof. If \(\Delta^-(D)=0\), then \(\gamma_{sdR}^2(D)=2n>4-n\). If \(\Delta^-(D)\ge 1\), then Theorem 5.1 implies \(\gamma_{sdR}^2(D)\ge 4-n\), and the lower bound is proved. If \(D=S_1\) or \(D=S_2\), then the function \(g\) with \(g(w)=3\) and \(g(x)=-1\) otherwise is an SDR2DF on \(D\) and hence \(\gamma_{sdR}^2(D)\le 4-n\). This shows that \(\gamma_{sdR}^2(D)=4-n\) in these cases.
Assume now that \(\gamma_{sdR}^2(D)=4-n\), and let \(f\) be a \(\gamma_{sdR}^2(D)\)-function. This implies that \(D\) has exactly one vertex \(u\) with \(f(u)=3\) and \(n-1\) vertices \(x_1,x_2,\ldots,x_{n-1}\) such that \(f(x_i)=-1\) for \(1\le i\le n-1\). It follows that \((u,x_i)\in A(D)\) for all \(1\le i\le n-1\). In addition, there is no arc \((x_i,x_j)\) for \(1\le i\neq j\le n-1\), and there may exist at most one additional arc \((x_t,u)\) for some integer \(t\) with \(1\le t\le n-1\). Consequently, \(D=S_1\) or \(D=S_2\). \(\square\)
Theorem 5.4. Let \(k\ge 3\) be an integer, and let \(D\) be a digraph of order \(n\) with \(\delta^-(D)\ge\lceil\frac{k}{3}\rceil-1\). Then \[\gamma_{sdR}^k(D)\ge k+\left\lceil\frac{k}{3}\right\rceil-n,\] with equality if and only if \(D=K_{\lceil\frac{k}{3}\rceil}^*\).
Proof. Since \(\Delta^-(D)\ge \delta^-(D)\ge \lceil\frac{k}{3}\rceil-1\), it follows from Theorem 5.1 that \[\gamma_{sdR}^k(D)\ge k+1+\Delta^-(D)-n\ge k+1+\left\lceil\frac{k}{3}\right\rceil-1-n=k+\left\lceil\frac{k}{3}\right\rceil-n,\] and the desired lower bound is proved.
If \(k>3\) and \(D=K_{\lceil\frac{k}{3}\rceil}^*\), then Corollary 1.3 implies that \[\gamma_{sdR}^k(D)=k=k+\left\lceil\frac{k}{3}\right\rceil-\left\lceil\frac{k}{3}\right\rceil\!.\]
If \(k=3\) and \(D=K_{\lceil\frac{k}{3}\rceil}^* = K_1^*\), then \(\gamma_{sdR}^3(K_1^*)= 3\) and the above equality holds.
Conversely, assume that \(\gamma_{sdR}^k(D)=k+\lceil\frac{k}{3}\rceil-n\), and let \(f\) be a \(\gamma_{sdR}^k(D)\)-function. If \(\Delta^-(D)\ge \lceil\frac{k}{3}\rceil\), then Theorem 5.1 implies \(\gamma_{sdR}^k(D)\ge k+\left\lceil\frac{k}{3}\right\rceil+1-n\), a contradiction. Thus, \(\Delta^-(D)=\delta^-(D)= \lceil\frac{k}{3}\rceil-1\). If there exists a vertex \(w\) with \(f(w)=-1\), then we obtain the following contradiction: \[k\le f(N^-[w])\le -1+3\Delta^-(D)=-1+3\left(\left\lceil\frac{k}{3}\right\rceil-1\right)\le k-2.\]
Hence \(f(x)\ge 1\) for each \(x\in V(D)\). Next, we distinguish three cases.
Case 1. Assume that \(k=3t\) for an integer \(t\ge 1\). If there exists a vertex \(w\) with \(1\le f(w)\le 2\), then we arrive at the contradiction \[k\le f(N^-[w])\le 2+3\Delta^-(D)=2+3\left(\frac{k}{3}-1\right)=k-1.\] Therefore, \(f(x)=3\) for all \(x\in V(D)\). We deduce that \(\omega(f)=3n=k+\frac{k}{3}-n\) and thus \(n=\frac{k}{3}\). Consequently, \(D=K_{\lceil\frac{k}{3}\rceil}^*\) in this case.
Case 2. Assume that \(k=3t+2\) for an integer \(t\ge 1\). If there exists a vertex \(w\) with \(f(w)=1\), then we arrive at the contradiction \[k\le f(N^-[w])\le 1+3\Delta^-(D)=1+3\left(\frac{k+1}{3}-1\right)=k-1.\]
Therefore, \(f(x)\ge 2\) for each \(x\in V(D)\).
If there exists a vertex \(w\) with \(f(w)=2\), then \(w\) has exactly \(\frac{k-2}{3}\) in-neighbors of weight 3. Suppose that, in addition to the vertex \(w\) and its \(\frac{k-2}{3}\) in-neighbors, \(D\) has \(a\ge 0\) further vertices of weight 2 and \(b\ge 0\) further vertices of weight 3. Then \(n=1+\frac{k-2}{3}+a+b\) and hence \[3n=3a+3b+k+1.\tag{1}\]
On the other hand, because \(D\) has \(a+1\) vertices of weight 2 and other vertices are of weight 3, we obtain \[\omega(f)=3n-(a+1)=k+\frac{k+1}{3}-n,\] and thus \[12n=4k+3a+4.\tag{2}\]
Combining (1) and (2), we find that \(9a+12b=0\) and therefore \(a=b=0\). It follows that \(n=\frac{k+1}{3}\) and hence \(D=K_{\lceil\frac{k}{3}\rceil}^*\).
Finally, assume that \(f(x)=3\) for each \(x\in V(D)\). Then \(\omega(f)=3n=k+\frac{k+1}{3}-n\), and we obtain the contradiction \(12n=4k+1\).
Case 3. Assume that \(k=3t+1\) for an integer \(t\ge 1\). If there exists a vertex \(w\) with \(f(w)=1\), then \(w\) has exactly \(\frac{k-1}{3}\) in-neighbors of weight 3. Suppose that \(D\) has \(a\ge 0\) further vertices of weight 1, \(b\ge 0\) further vertices of weight 2 and \(c\ge 0\) further vertices of weight 3. Then \(n=1+\frac{k-1}{3}+a+b+c\) and hence \[3n=3a+3b+3c+k+2.\tag{3}\]
On the other hand, \(\omega(f)=3n-2(a+1)-b=k+\frac{k+2}{3}-n\) and thus \[12n=4k+6a+3b+8.\tag{4}\] Eqs. (3) and (4) imply that \(6a+9b+12c=0\), and hence \(a=b=c=0\). We deduce that \(n=\frac{k+2}{3}\), and therefore \(D=K_{\lceil\frac{k}{3}\rceil}^*\).
It remains to consider the case where \(f(x)\ge 2\) for each \(x\in V(D)\). If there exists a vertex \(w\) with \(f(w)=2\), then \(w\) has exactly \(\frac{k-1}{3}\) in-neighbors of weight 3 or \(\frac{k-1}{3}-1\) in-neighbors of weight 3 and one in-neighbor of weight 2. Assume first that \(w\) has exactly \(\frac{k-1}{3}\) in-neighbors of weight 3. Suppose that \(D\) has \(a\ge 0\) further vertices of weight 2 and \(b\ge 0\) further vertices of weight 3. Then \(n=1+\frac{k-1}{3}+a+b\) and hence \[3n=3a+3b+k+2.\tag{5}\]
In addition, \(\omega(f)=3n-(a+1)=k+\frac{k+2}{3}-n\) and therefore \[12n=4k+3a+5.\tag{6}\]
Now, Eqs. (5) and (6) lead to the contradiction \(9a+12b+3=0\). Assume second that \(w\) has \(\frac{k-1}{3}-1\) in-neighbors of weight 3 and one in-neighbor of weight 2. Suppose that \(D\) has \(a\ge 0\) further vertices of weight 2 and \(b\ge 0\) further vertices of weight 3. Then \(n=1+\frac{k-1}{3}+a+b\) and therefore \[3n=3a+3b+k+2.\tag{7}\]
In addition, \(\omega(f)=3n-(a+2)=k+\frac{k+2}{3}-n\) and hence \[12n=4k+3a+8.\tag{8}\]
It follows from (7) and (8) that \(9a+12b=0\) and therefore \(a=b=0\). Hence \(n=\frac{k+2}{3}\) and we obtain \(D=K_{\lceil\frac{k}{3}\rceil}^*\).
Finally, assume that \(f(x)=3\) for each \(x\in V(D)\). Then \(\omega(f)=3n=k+\frac{k+2}{3}-n\), and we obtain the contradiction \(12n=4k+2\). This completes the proof. \(\square\)
A digraph is connected if its underlying graph is connected. A rooted tree is a connected digraph with a vertex \(r\) of in-degree 0, called the root, such that every vertex different from the root has in-degree 1.
Proposition 5.5. If \(T\) is a rooted tree of order \(n\ge 2\), then \(\gamma_{sdR}^3(T)\ge n+2\), with equality if and only if \(T=S_1\).
Proof. Let \(f\) be a \(\gamma_{sdR}^3(T)\)-function, and let \(r\) be the root of \(T\). Since \(d^-(r)=0\) and \(d^-(x)=1\) for \(x\in V(T)\setminus\{r\}\), we note that \(f(r)=3\) and \(f(x)\ge 1\) for \(x\in V(T)\setminus\{r\}\). Therefore, \(\gamma_{sdR}^3(T)\ge 3+(n-1)= n+2\), and the desired bound is proved.
If \(T\ne S_1\), then there exist two vertices \(u\) and \(v\) such that \(r\) dominates \(u\) and \(u\) dominates \(v\). Since \(f(u)=f(v)=1\) is not possible, we note that \(f(u)\ge 2\) or \(f(v)\ge 2\). Therefore, \(\gamma_{sdR}^3(T)=\omega(f)\ge 3+2+(n-2)=n+3\) when \(T\neq S_1\).
If \(T=S_1\), then we define the function \(g:V(T)\rightarrow\{-1,1,2,3\}\) as follows: \(g(r)=3\) and \(g(x)=1\) for all \(x\in V(T)\setminus\{r\}\). We have \(g(N^-[y])\ge 3\) for any vertex \(y\) in \(T\) and every vertex of weight 1 has an in-neighbor of weight 3, therefore this function is an SDR3DF on \(T\) of weight \(\omega(g)=n+2\). Hence \(\gamma_{sdR}^3(S_1)\le n+2\) and thus \(\gamma_{sdR}^3(S_1)=n+2\). \(\square\)