Electronic Journal of Graph Theory and Applications

Seyed Mahmoud Sheikholeslami^a, Lutz Volkmann^b

^aDepartment of Mathematics Azarbaijan Shahid Madani University Tabriz, I.R. Iran ^bLehrstuhl II für Mathematik RWTH Aachen University 52056 Aachen, Germany

s.m.sheikholeslami@azaruniv.edu, volkm@math2.rwth-aachen.de

A signed Roman dominating function on the digraph D is a function \(f:V(D) \longrightarrow \{-1,1,2\}\) such that \(\sum_{u \in N^-[v]} f(u) \ge 1\) for every \(v \in V(D)\), where \(N^-[v]\) consists of v and all inner neighbors of v, and every vertex \(u \in V(D)\) for which f(u) = -1 has an inner neighbor v for which f(v) = 2. A set \(\{f_1, f_2, \ldots, f_d\}\) of distinct signed Roman dominating functions on D with the property that \(\sum_{i=1}^d f_i(v) \le 1\) for each \(v \in V(D)\), is called a signed Roman dominating family (of functions) on D. The maximum number of functions in a signed Roman dominating family on D is the signed Roman domatic number of D, denoted by \(d_{sR}(D)\). In this paper we initiate the study of signed Roman domatic number in digraphs and we present some sharp bounds for \(d_{sR}(D)\). In addition, we determine the signed Roman domatic number of some digraphs. Some of our results are extensions of well-known properties of the signed Roman domatic number of graphs.

Keywords: Digraph, signed Roman dominating function, signed Roman domination number, signed Roman domatic number Mathematics Subject Classification: 05C20, 05C69 DOI: 10.5614/ejgta.2015.3.1.9

Received: 19 July 2014, Revised: 17 March 2015, Accepted: 21 March 2015.

1. Introduction

In this paper we continue the study of Roman dominating functions in graphs and digraphs. Let G be a finite and simple graph with vertex set V(G), and let \(N_G[v] = N[v]\) be the closed neighborhood of the vertex v. A signed Roman dominating function (SRDF) on a graph G is defined in [1] as a function \(f: V(G) \longrightarrow \{-1,1,2\}\) such that \(\sum_{x \in N[v]} f(x) \ge 1\) for each \(v \in V(G)\), and every vertex \(u \in V(D)\) for which f(u) = -1 is adjacent to a vertex v with f(v) = 2. The weight of an SRDF f is the value \(\omega(f) = \sum_{v \in V(G)} f(v)\). The signed Roman domination number \(\gamma_{sR}(G)\) of G is the minimum weight of an SRDF on G. A set \(\{f_1, f_2, \ldots, f_d\}\) of distinct signed Roman dominating functions on G with the property that \(\sum_{i=1}^d f_i(v) \le 1\) for each \(v \in V(G)\), is called a signed Roman dominating family (of functions) on G. The maximum number of functions in a signed Roman dominating family (SRD family) on G is the signed Roman domatic number of G, denoted by \(d_{sR}(G)\). This parameter was introduced and investigated in [4].

Let D be a finite and simple digraph with vertex set V = V(D) and arc set A = A(D). The order |V| of D is denoted by n = n(D), and the size |A| is denoted by m = m(D). 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, we also say that x dominates y and y is dominated by x. We write \(d_D^+(v) = d^+(v)\) for the out-degree of a vertex v and \(d_D^-(v) = d^-(v)\) for its in-degree. The minimum and maximum in-degree are \(\delta^-(D) = \delta^-\) and \(\Delta^-(D) = \Delta^-\) and the minimum and maximum out-degree are \(\delta^{+}(D) = \delta^{+} \text{ and } \Delta^{+}(D) = \Delta^{+}.\) The sets \(N_{D}^{-}(v) = N^{-}(v) = \{x | (x,v) \in A(D)\}\) and \(N_D^+(v) = N^+(v) = \{x | (v,x) \in A(D)\}\) are called the in-neighborhood and out-neighborhood of the vertex v. Likewise, \(N_D^+[v] = N^+[v] = N^+(v) \cup \{v\}\) and \(N_D^-[v] = N^-[v] = N^-(v) \cup \{v\}\). If \(X \subseteq V(D)\), then D[X] is the subdigraph induced by X. A digraph D is r-in-regular when \(\delta^-(D) = \Delta^-(D) = r\) and r-out-regular when \(\delta^+(D) = \Delta^+(D) = r\). If D is r-in-regular and r-out-regular, then D is called r-regular. The associated digraph \(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 end as e. For a real-valued function \(f:V(D)\longrightarrow \mathbb{R}\), the weight of f is \(\omega(f)=\sum_{v\in V(D)}f(v)\), and for \(S \subseteq V(D)\), we define \(f(S) = \sum_{v \in S} f(v)\), so \(\omega(f) = f(V(D))\). Consult Haynes, Hedetniemi and Slater [2, 3] for notation and terminology which are not defined here.

A signed Roman dominating function (SRDF) on a digraph D is defined in [5] as a function \(f:V(D)\longrightarrow \{-1,1,2\}\) such that \(f(N^-[v])=\sum_{x\in N^-[v]}f(x)\geq 1\) for each \(v\in V(D)\), and such that every vertex \(u\in V(D)\) for which f(u)=-1 has an in-neighbor v for which f(v)=2. The weight of an SRDF f is the value \(\omega(f)=\sum_{v\in V(D)}f(v)\). The signed Roman domination number of a digraph D, denoted by \(\gamma_{sR}(D)\), equals the minimum weight of an SRDF on D. A \(\gamma_{sR}(D)\)-function is a signed Roman dominating function of D with weight \(\gamma_{sR}(D)\). A signed Roman dominating function \(f:V(D)\longrightarrow \{-1,1,2\}\) can be represented by the ordered partition \((V_{-1},V_1,V_2)\) (or \((V_{-1}^f,V_1^f,V_2^f)\) to refer f) of V(D), where \(V_i=\{v\in V(D)\mid f(v)=i\}\). In this representation, its weight is \(\omega(f)=|V_1|+2|V_2|-|V_{-1}|\).

A set \(\{f_1, f_2, \dots, f_d\}\) of distinct signed Roman dominating functions on D with the property that \(\sum_{i=1}^d f_i(v) \leq 1\) for each \(v \in V(D)\), is called a signed Roman dominating family (of functions)

on D. The maximum number of functions in a signed Roman dominating family (SRD family) on D is the signed Roman domatic number of D, denoted by \(d_{sR}(D)\). The signed Roman domatic number is well-defined and

\[d_{sR}(D) \ge 1 \tag{1}\]

for all digraphs D, since the set consisting of the SRDF with constant value 1 forms an SRD family on D.

Our purpose in this paper is to initiate the study of signed Roman domatic number in digraphs. We study basic properties and bounds for the signed Roman domatic number of a digraph. In addition, we determine the signed Roman domatic number of some classes of digraphs. Some of our results are extensions of well-known properties of the signed Roman domatic number \(d_{sR}(G)\) of graphs G.

We make use of the following results in this paper.

Proposition A. ([4]) If \(K_n\) is the complete graph of order \(n \ge 1\), then \(d_{sR}(K_n) = n\), unless n = 3 in which case \(d_{sR}(K_n) = 1\).

Proposition B. ([5]) If \(K_n^*\) is the complete digraph of order \(n \geq 1\), then \(\gamma_{sR}(K_n^*) = 1\), unless n = 3 in which case \(\gamma_{sR}(K_n^*) = 2\).

Proposition C. ([5]) Let D be a digraph of order \(n \ge 1\). Then \(\gamma_{sR}(D) \le n\), with equality if and only if D is the disjoint union of isolated vertices and oriented triangles \(C_3\).

Proposition D. ([5]) If D is an r-out-regular digraph of order n with \(r \geq 1\), then \(\gamma_{sR}(D) \geq n/(r+1)\).

Proposition E. ([5]) Let \(C_n\) be an oriented cycle of order \(n \ge 2\). Then \(\gamma_{sR}(C_n) = n/2\) when n is even and \(\gamma_{sR}(C_n) = (n+3)/2\) when n is odd.

Proposition F. ([5]) Let \(K_{p,p}^*\) be the complete bipartite digraph of order \(n=2p\geq 2\). Then \(\gamma_{sR}(K_{1,1}^*)=1\) \(\gamma_{sR}(K_{2,2}^*)=3\) and \(\gamma_{sR}(K_{p,p}^*)=4\) when \(p\geq 3\).

Since \(N_{G^*}^-[v] = N_G[v]\) for each \(v \in V(G) = V(G^*)\), the following useful observation is valid.

Observation 1.1. If \(G^*\) is the associated digraph of a graph G, then \(\gamma_{sR}(G^*) = \gamma_{sR}(G)\) and \(d_{sR}(G^*) = d_{sR}(G)\).

Using Observation 1.1 and Proposition A, we obtain the signed Roman domatic number of complete digraphs.

Corollary 1.1. If \(K_n^*\) is the complete digraph of order \(n \ge 1\), then \(d_{sR}(K_n^*) = n\), unless n = 3 in which case \(d_{sR}(K_n^*) = 1\).

2. Properties of the signed Roman domatic number

In this section we present basic properties of \(d_{sR}(D)\) and sharp bounds on the signed Roman domatic number of a digraph.

Theorem 2.1. For every digraph D,

\[d_{sR}(D) < \delta^{-}(D) + 1.\]

Moreover, if \(d_{sR}(D) = \delta^-(D) + 1\), then for each SRD family \(\{f_1, f_2, \dots, f_d\}\) on D with \(d = d_{sR}(D)\) and each vertex v of minimum in-degree, \(\sum_{u \in N^-[v]} f_i(u) = 1\) for each function \(f_i\) and \(\sum_{i=1}^d f_i(u) = 1\) for all \(u \in N^-[v]\).

Proof. Let \(\{f_1, f_2, \dots, f_d\}\) be an SRD family on D such that \(d = d_{sR}(D)\). Assume that v is a vertex of minimum in-degree \(\delta^-(D)\). It is easy to see that

\[d \le \sum_{i=1}^{d} \sum_{u \in N^{-}[v]} f_i(u) = \sum_{u \in N^{-}[v]} \sum_{i=1}^{d} f_i(u) \le \sum_{u \in N^{-}[v]} 1 = \delta^{-}(D) + 1.\]

Thus \(d_{sR}(D) \leq \delta^{-}(D) + 1\).

If \(d_{sR}(D) = \delta^-(D) + 1\), then the two inequalities occurring in the proof become equalities. Hence for the SRD family \(\{f_1, f_2, \dots, f_d\}\) on D and for each vertex v of minimum in-degree, \(\sum_{u \in N^-[v]} f_i(u) = 1\) for each function \(f_i\) and \(\sum_{i=1}^d f_i(u) = 1\) for all \(u \in N^-[v]\).

Inequality (1) and Theorem 2.1 imply the next result immediately.

Corollary 2.1. If D consists of isolated vertices or D is an oriented path, then \(d_{sR}(D) = 1\).

A leaf of a graph G is a vertex of degree 1, while a support vertex of G is a vertex adjacent to a leaf. The set of leaves incident to a support vertex v is denoted by \(L_v\).

Proposition 2.1. If G has a support vertex v of degree at least two with \(|L_v| \ge (2 \deg(v) + 2)/3\), then \(d_{sR}(G^*) = 1\).

Proof. It follows from Theorem 2.1 that \(d_{sR}(G^*) \leq 2\). Suppose to the contrary that \(d_{sR}(G^*) = 2\) and assume that \(\{f_1, f_2\}\) is an SRD family on \(G^*\). Let \(L_v = \{u_1, \ldots, u_k\}\). Theorem 2.1 implies that \(f_1(v) + f_2(v) = 1\). Since \(f_j(x) \in \{-1, 1, 2\}\) for each j and each vertex x, we deduce that \(f_1(v) = -1\) and \(f_2(v) = 2\) or \(f_1(v) = 2\) and \(f_2(v) = -1\). Assume, without loss of generality, that \(f_1(v) = -1\) and \(f_2(v) = 2\). By Theorem 2.1, we must have \(f_2(u_i) + f_2(v) = 1\) for each \(1 \leq i \leq k\) and therefore \(f_2(u_i) = -1\) for each \(1 \leq i \leq k\). Since \(|L_v| \geq (2 \deg(v) + 2)/3\), we obtain the contradiction \(1 \leq \sum_{x \in N^-[v]} f_2(x) \leq 0\). Thus \(d_{sR}(G^*) = 1\).

Corollary 2.2. For \(n \geq 2\), \(d_{sR}(K_{1,n}^*) = 1\).

Theorem 2.2. If D is a digraph of order n, then

\[\gamma_{sR}(D) \cdot d_{sR}(D) \le n.\]

Moreover, if \(\gamma_{sR}(D) \cdot d_{sR}(D) = n\), then for each SRD family \(\{f_1, f_2, \dots, f_d\}\) on D with \(d = d_{sR}(D)\), each function \(f_i\) is a \(\gamma_{sR}(D)\)-function and \(\sum_{i=1}^d f_i(v) = 1\) for all \(v \in V(D)\).

Proof. Let \(\{f_1, f_2, \dots, f_d\}\) be an SRD family on D such that \(d = d_{sR}(D)\) and let \(v \in V(D)\). Then

\[d \cdot \gamma_{sR}(D) = \sum_{i=1}^{d} \gamma_{sR}(D) \le \sum_{i=1}^{d} \sum_{v \in V(D)} f_i(v) = \sum_{v \in V(D)} \sum_{i=1}^{d} f_i(v) \le \sum_{v \in V(D)} 1 = n.\]

If \(\gamma_{sR}(D) \cdot d_{sR}(D) = n\), then the two inequalities occurring in the proof become equalities. Hence for the SRD family \(\{f_1, f_2, \dots, f_d\}\) on D and for each i, \(\sum_{v \in V(D)} f_i(v) = \gamma_{sR}(D)\). Thus each function \(f_i\) is a \(\gamma_{sR}(D)\)-function, and \(\sum_{i=1}^d f_i(v) = 1\) for all \(v \in V(D)\).

The next result follows immediately from Theorem 2.2 and Proposition C, and it demonstrates that Theorem 2.2 is sharp.

Corollary 2.3. Let D be a digraph of order \(n \ge 1\). Then \(\gamma_{sR}(D) = n\) and \(d_{sR}(D) = 1\) if and only if D consists of the disjoint union of isolated vertices and oriented triangles \(C_3\).

Applying Proposition E and Theorems 2.1 and 2.2, we obtain the signed Roman domatic number for oriented cycles.

Corollary 2.4. Let \(C_n\) be an oriented cycle of length \(n \ge 2\). Then \(d_{sR}(C_n) = 1\) when n is odd and \(d_{sR}(C_n) = 2\) when n is even.

Proof. First let n be odd. Using Proposition E and Theorem 2.2, we deduce that

\[d_{sR}(C_n) \le \frac{n}{\gamma_{sR}(C_n)} = \frac{2n}{n+3} < 2\]

and thus \(d_{sR}(C_n) = 1\).

Now let n=2p be even, and let \(C_n=u_1v_1u_2v_2\dots u_pv_pu_1\). Define the functions \(f_i:V(C_n)\longrightarrow \{-1,1,2\}\) by \(f_1(u_i)=-1\) and \(f_1(v_i)=2\) and \(f_2(u_i)=2\) and \(f_2(v_i)=-1\) for \(1\leq i\leq p\). Then \(f_1\) and \(f_2\) are SRDF such that \(f_1(x)+f_2(x)=1\) for each vertex \(x\in V(C_n)\). Therefore \(d_{sR}(C_n)\geq 2\). It follows from Theorem 2.1 that \(d_{sR}(C_n)\leq 2\), and so \(d_{sR}(C_n)=2\) when n is even.

Theorem 2.3. Let \(p \geq 4\) be an even integer. Then \(d_{sR}(K_{p,p}^*) = \frac{p}{2}\) when \(p \neq 6\).

Proof. According to Theorem 2.2 and Proposition F, we have

\[d_{sR}(K_{p,p}^*) \le \frac{2p}{\gamma_{sR}(K_{p,p}^*)} = \frac{p}{2}\]

for \(p \geq 3\).

Assume first that p=6t+4 for an integer \(t\geq 0\). Let \(\{u_1,v_1,u_2,v_2,\ldots,u_{3t+2},v_{3t+2}\}\) and \(\{a_1,b_1,a_2,b_2,\ldots,a_{3t+2},b_{3t+2}\}\) be the partite sets of \(D=K_{p,p}^*\). For \(1\leq i\leq 3t+2\) define the function \(g_i:V(D)\longrightarrow \{-1,1,2\}\) by

\[g_i(u_i) = g_i(v_i) = g_i(u_{i+1}) = g_i(v_{i+1}) = \dots = g_i(u_{2t+i}) = g_i(v_{2t+i}) = -1,\]
\(g_i(a_i) = g_i(b_i) = g_i(a_{i+1}) = g_i(b_{i+1}) = \dots = g_i(a_{2t+i}) = g_i(b_{2t+i}) = -1\)

and \(g_i(x)=2\) otherwise, where the indices are taken modulo p/2=3t+2. Then \(g_i\) is an SRDF on D for \(1 \leq i \leq 3t+2\) such that \(\sum_{i=1}^{3t+2} g_i(x)=1\) for each vertex \(x \in V(D)\). Therefore \(\{g_1,g_2,\ldots,g_{3t+2}\}\) is a signed Roman dominating family on \(K_{p,p}^*\). It follows that \(d_{sR}(K_{p,p}^*)\geq 3t+2=\frac{p}{2}\) and thus \(d_{sR}(K_{p,p}^*)=\frac{p}{2}\).

Assume second that p=6t for an integer \(t\geq 2\). Now let \(\{u_1,v_1,u_2,v_2,\ldots,u_{3t},v_{3t}\}\) and \(\{a_1,b_1,a_2,b_2,\ldots,a_{3t},b_{3t}\}\) be the partite sets of \(D=K_{p,p}^*\). For \(1\leq i\leq 3t\) define the function \(g_i:V(D)\longrightarrow \{-1,1,2\}\) by

\[g_i(u_i) = g_i(v_i) = g_i(u_{i+1}) = g_i(v_{i+1}) = \dots = g_i(u_{2t-i}) = g_i(v_{2t-i}) = -1,\] \[g_i(a_i) = g_i(b_i) = g_i(a_{i+1}) = g_i(b_{i+1}) = \dots = g_i(a_{2t-i}) = g_i(b_{2t-i}) = -1,\] \[g_i(u_{2t+1-i}) = g_i(v_{2t+1-i}) = g_i(u_{2t+2-i}) = g_i(v_{2t+2-i}) = 1,\] \[g_i(a_{2t+1-i}) = g_i(b_{2t+1-i}) = g_i(a_{2t+2-i}) = g_i(b_{2t+2-i}) = 1\]

and \(g_i(x)=2\) otherwise, where the indices are taken modulo p/2=3t. Then \(g_i\) is an SRDF on D for \(1 \leq i \leq 3t\) such \(\sum_{i=1}^{3t} g_i(x)=1\) for each vertex \(x \in V(D)\). Therefore \(\{g_1,g_2,\ldots,g_{3t}\}\) is a signed Roman dominating family on \(K_{p,p}^*\). It follows that \(d_{sR}(K_{p,p}^*)\geq 3t=\frac{p}{2}\) and thus \(d_{sR}(K_{p,p}^*)=\frac{p}{2}\).

Assume third that p=6t+2 for an integer \(t\geq 1\). Let \(\{u_1,v_1,u_2,v_2,\ldots,u_{3t+1},v_{3t+1}\}\) and \(\{a_1,b_1,a_2,b_2,\ldots,a_{3t+1},b_{3t+1}\}\) be the partite sets of \(D=K_{p,p}^*\). For \(1\leq i\leq 3t+1\) define the function \(g_i:V(D)\longrightarrow \{-1,1,2\}\) by

\[g_i(u_i) = g_i(v_i) = g_i(u_{i+1}) = g_i(v_{i+1}) = \dots = g_i(u_{2t+1-i}) = g_i(v_{2t+1-i}) = -1,\]
\[g_i(a_i) = g_i(b_i) = g_i(a_{i+1}) = g_i(b_{i+1}) = \dots = g_i(a_{2t+1-i}) = g_i(b_{2t+1-i}) = -1,\]
\[g_i(u_{2t+2-i}) = g_i(v_{2t+2-i}) = g_i(a_{2t+2-i}) = g_i(b_{2t+2-i}) = 1\]

and \(g_i(x)=2\) otherwise, where the indices are taken modulo p/2=3t+1. Then \(g_i\) is an SRDF on D for \(1\leq i\leq 3t+1\) such \(\sum_{i=1}^{3t+1}g_i(x)=1\) for each vertex \(x\in V(D)\). Therefore \(\{g_1,g_2,\ldots,g_{3t+1}\}\) is a signed Roman dominating family on \(K_{p,p}^*\). It follows that \(d_{sR}(K_{p,p}^*)\geq 3t+1=\frac{p}{2}\) and thus \(d_{sR}(K_{p,p}^*)=\frac{p}{2}\).

Theorem 2.3 is a further example which shows that Theorem 2.2 is sharp.

Theorem 2.4. If D is a digraph of order n ≥ 1, then

\[\gamma_{sR}(D) + d_{sR}(D) \le n + 1 \tag{2}\]

with equality if and only if D = K^∗ n (n 6= 3) or D consists of the disjoint union of isolated vertices and oriented triangles.

Proof. It follows from Theorem 2.2 that

\[\gamma_{sR}(D) + d_{sR}(D) \le \frac{n}{d_{sR}(D)} + d_{sR}(D). \tag{3}\]

According to inequality (1) and Theorem 2.1, we have 1 ≤ dsR(D) ≤ n. Using these bounds, and the fact that the function g(x) = x + n/x is decreasing for 1 ≤ x ≤ √ n and increasing for √ n ≤ x ≤ n, the last inequality leads to the desired bound immediately.

If D = K^∗ n (n 6= 3) then we deduce from Proposition B and Corollary 1.1 that γsR(D) + dsR(D) = n+ 1. If D consists of the disjoint union of isolated vertices and oriented triangles, then it follows from Proposition C and (1) that γsR(D) +dsR(D) ≥ n+ 1 and thus γsR(D) +dsR(D) = n + 1 by (2).

Conversely, let equality hold in (2). It follows from (3) that

\[n+1 = \gamma_{sR}(D) + d_{sR}(D) \le \frac{n}{d_{sR}(D)} + d_{sR}(D) \le n+1,\]

which implies that γsR(D) = n and dsR(D) = 1 or dsR(D) = n and γsR(D) = 1. If γsR(D) = n, then Proposition C shows that D consists of the disjoint union of isolated vertices and oriented triangles. If dsR(G) = n and γsR(D) = 1, then Theorem 2.1 implies that δ ⁻(D) = n − 1 and hence D is a complete digraph K^∗ n . Since also γsR(D) = 1, we conclude from Proposition B that n 6= 3 and hence D = K^∗ n (n 6= 3).

The complement D of a digraph D is the digraph with vertex set V (D) such that for any two distinct vertices u, v the arc (u, v) belongs to D if and only if (u, v) does not belong to D. As an application of Theorems 2.1, we will prove the following Nordhaus-Gaddum type result.

Theorem 2.5. For every digraph D of order n,

\[d_{sR}(D) + d_{sR}(\overline{D}) \le n + 1. \tag{4}\]

Furthermore, if dsR(D) + dsR(D) = n + 1, then D is in-regular.

Proof. Since δ ⁻(D) = n − 1 − ∆⁻(D), it follows from Theorem 2.1 that

\[d_{sR}(D) + d_{sR}(\overline{D}) \leq (\delta^{-}(D) + 1) + (\delta^{-}(\overline{D}) + 1)\]
= \((\delta^{-}(D) + 1) + (n - 1 - \Delta^{-}(D) + 1) \leq n + 1.\)

If D is not in-regular, then ∆⁻(D) − δ ⁻(D) ≥ 1, and hence the above inequality chain implies the better bound dsR(D) + dsR(D) ≤ n.

Using Observation 1.1, Theorems 2.1, 2.2, 2.4 or 2.5, we obtain the next known results.

Corollary 2.5. ([4]) Let G be a graph of order n. Then \(d_{sR}(G) \leq \delta(G) + 1\), \(\gamma_{sR}(G) \cdot d_{sR}(G) \leq n\), \(\gamma_{sR}(G) + d_{sR}(G) \leq n + 1\) and \(d_{sR}(G) + d_{sR}(\overline{G}) \leq n + 1\).

For some out-regular graphs we will improve the upper bound given in Theorem 2.1.

Theorem 2.6. Let D be an r-out-regular digraph of order n such that \(r \ge 1\). If \(n \not\equiv 0 \pmod{(r+1)}\), then \(d_{sR}(D) \le r\).

Proof. Since \(n \not\equiv 0 \pmod{(r+1)}\), we deduce that n = p(r+1) + t with integers \(p \geq 1\) and \(1 \leq t \leq r\). Let \(\{f_1, f_2, \dots, f_d\}\) be an SRD family on D such that \(d = d_{sR}(D)\). It follows that

\[\sum_{i=1}^{d} \omega(f_i) = \sum_{i=1}^{d} \sum_{v \in V} f_i(v) = \sum_{v \in V} \sum_{i=1}^{d} f_i(v) \le \sum_{v \in V} 1 = n.\]

Proposition D implies \(\omega(f_i) \geq \gamma_{sR}(D) \geq p+1\) for each \(i \in \{1, 2, ..., d\}\). If we suppose to the contrary that \(d \geq r+1\), then the above inequality chain leads to the contradiction

\[n \ge \sum_{i=1}^{d} \omega(f_i) \ge d(p+1) \ge (r+1)(p+1) = p(r+1) + r + 1 > n.\]

Thus \(d \leq r\), and the proof is complete.

Corollary 1.1 demonstrates that Theorem 2.6 is not valid in general when \(n \equiv 0 \pmod{(r+1)}\). As an application of Theorem 2.6, we improve Theorem 2.5 for r-regular digraphs.

Theorem 2.7. Let D be an r-regular digraph of order n. Then \(d_{sR}(D) + d_{sR}(\overline{D}) = n + 1\) if and only if \(D = K_n^*\) or \(\overline{D} = K_n^*\) and \(n \neq 3\).

Proof. If \(n \neq 3\) and \(D = K_n^*\) or \(\overline{D} = K_n^*\), then Corollaries 1.1 and 2.1 lead to \(d_{sR}(D) + d_{sR}(\overline{D}) = n + 1\).

Conversely, assume that \(d_{sR}(D) + d_{sR}(\overline{D}) = n + 1\). Since D is r-regular, \(\overline{D}\) is (n - 1 - r)-regular. If r = 0 or r = n - 1, then \(D = K_n^*\) or \(\overline{D} = K_n^*\), and we obtain the desired result.

Next assume that \(1 \le r \le n-2\) and \(1 \le \delta(\overline{D}) = n-1-r \le n-2\). We assume, without loss of generality, that \(r \le (n-1)/2\). If \(n \not\equiv 0 \pmod{(r+1)}\), then it follows from Theorems 2.1 and 2.6 that

\[n+1 = d_{sR}(D) + d_{sR}(\overline{D}) \le \delta^{-}(D) + (\delta^{-}(\overline{D}) + 1) = r + (n-1-r+1) = n,\]

a contradiction. Next assume that \(n \equiv 0 \pmod{(r+1)}\). Then n = p(r+1) with an integer \(p \ge 2\). If \(n \not\equiv 0 \pmod{(n-r)}\), then it follows from Theorems 2.1 and 2.6 that

\[n+1 = d_{sR}(D) + d_{sR}(\overline{D}) \le (r+1) + (n-1-r) = n,\]

a contradiction. Therefore assume that \(n \equiv 0 \pmod{(n-r)}\). Then n = q(n-r) with an integer \(q \ge 2\). Since \(r \le (n-1)/2\), this leads to the contradiction

\[n = q(n-r) \ge q\left(n - \frac{n-1}{2}\right) = \frac{q(n+1)}{2} \ge n+1,\]

and the proof is complete.

Corollary 2.6. If T is a tournament of odd order n ≥ 3, then dsR(T) + dsR(T) ≤ n − 1.

Proof. If T is an r-regular tournament, then T is also an r-regular tournament such that n = 2r+1. Therefore it follows from Theorem 2.6 that dsR(T) + dsR(T) ≤ r + r = n − 1.

Assume now that T is not regular. Then δ ⁻(T) ≤ (n − 3)/2 and δ ⁻(T) ≤ (n − 3)/2, and we deduce from Theorem 2.1 that

\[d_{sR}(T) + d_{sR}(\overline{T}) \le (\delta^{-}(T) + 1) + (\delta^{-}(\overline{T}) + 1) \le \left(\frac{n-1}{2}\right) + \left(\frac{n-1}{2}\right) = n-1.\]

References

• [1] H.A. Ahangar, M.A. Henning, Y. Zhao, C. L¨owenstein and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014), 241–255.
• [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
• [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, Inc. New York, 1998.
• [4] S.M. Sheikholeslami and L. Volkmann, The signed Roman domatic number of a graph, Ann. Math. Inform. 40 (2012), 105-112.
• [5] S.M. Sheikholeslami and L. Volkmann, Signed Roman domination in digraphs, J. Comb. Optim. DOI 10.1007/s10878-013-9648-2.