Electronic Journal of Graph Theory and Applications

Lyes Ouldrabah^a, Mostafa Blidia^a, Ahmed Bouchou^b

^aLamda-RO, Department of Mathematics, University of Blida 1. B.P. 270, Blida, Algeria

lyes.ouldrabah@gmail.com, m_blidia@yahoo.fr, bouchou.ahmed@yahoo.fr

Let D=(V,A) be a digraph of order n=|V|. A Roman dominating function of a digraph D is a function \(f:V\longrightarrow \{0,1,2\}\) such that every vertex u for which f(u)=0 has an inneighbor v for which f(v)=2. The weight of a Roman dominating function is the value \(f(V)=\sum_{u\in V}f(u)\). The minimum weight of a Roman dominating function of a digraph D is called the Roman domination number of D, denoted by \(\gamma_R(D)\). In this paper, we characterize oriented trees T satisfying \(\gamma_R(T)+\Delta^+(T)=n+1\).

Keywords: Roman domination, digraph, oriented tree 2010 Mathematics Subject Classification: 05C20, 05C69

DOI: 10.5614/ejgta.2021.9.1.9

1. Introduction

The digraph D=(V,A) of order n=|V| considered here has no loops and no multiple arcs (but pairs of opposite arcs are allowed). If \((u,v)\in A\), then we write \(u\to v\) and we say that v is an out-neighbor (successor) of u, (or u dominates v) and u is an in-neighbor (predecessor) of v, and if \((u,v)\notin A\), we write \(u\to v\). If \(u\to v\) and \(v\to u\), we say that (u,v) is a symmetrical arc and we write \(v\longleftrightarrow u\). If \(v\to v\) and \(v\to v\), we say that \(v\to v\) is an asymmetrical arc and we write \(v\to v\). Also, if \(v\to v\) and \(v\to v\) and \(v\to v\), then we write \(v\to v\). Let \(v\to v\) be a non-empty set and \(v\to v\) are non adjacent (\(v\to v\) and \(v\to v\)), then we write \(v\to v\). Let \(v\to v\) be a non-empty set and \(v\to v\) are non-empty set and \(v\to v\). If \(v\to v\) is in-neighbor of each vertex of \(v\to v\), then we use the notation \(v\to v\to v\).

A digraph H=(U,B) is the subdigraph of D whenever \(U\subseteq V(D)\) and \(B\subseteq A(D)\), the subdigraph induced by U is denoted by \(\langle U\rangle\). If U=V(D), the subdigraph is said to be spanning.

Received: 3 March 2018, Revised: 14 December 2020, Accepted: 30 December 2020.

^&lt;sup>b</sup>Department of Mathematics, University of Medea, Algeria

An oriented graph is a digraph D = (V, A) containing no symmetric pair of arcs. That can be obtained from a graph G by assigning a direction to each edge of G. The resulting digraph D is called an orientation of G. Thus, if D is an oriented graph, then for every pair u and v of distinct vertices of D, either (u, v) or (v, u) is an arc of D, but not both.

A tree is a connected graph without cycles. Also, an oriented tree is a connected oriented graph without oriented cycle. Note that an oriented tree with n vertices has n-1 arcs.

Define the out-neighborhood of a vertex \(v \in V\) as \(N_D^+(v) = \{u \in V : v \to u\}\), the inneighborhood of v as \(N_D^-(v) = \{w \in V : w \to v\}\). We define \(N_D^+[v] = N_D^+(v) \cup \{v\}\) and \(N_D^-[v] = N_D^-(v) \cup \{v\}\). Also, for a subset \(S \subseteq V\), \(N_D^+(S) = \cup_{v \in S} N_D^+(v)\) and \(N_D^+[S] = N_D^+(S) \cup S\). The definition of \(N_D^-(S)\), \(N_D^-[S]\) are similar. The out-degree of a vertex v in D is defined as \(d_D^+(v) = |N_D^+(v)|\). The maximum (respectively, minimum) out-degree of D is given by \(D_D^+(V) = \max\{d_D^+(v) : v \in V\}\) (respectively, \(D_D^+(V) = \min\{d_D^+(v) : v \in V\}\)). Similarly, the in-degree of D is \(D_D^-(V) = \max\{d_D^-(V) : v \in V\}\) (respectively, \(D_D^-(V) = \min\{d_D^-(V) : v \in V\}\)). For a vertex D0 in the set D1, the out-private neighbors of D2 with respect to D3 is the set D4, and notations not defined here, we refer the reader to the book by Haynes et al. [6].

A Roman dominating function (RDF) on a digraph D=(V,A) is a function \(f:V\longrightarrow\{0,1,2\}\) such that every vertex u for which f(u)=0 is a successor of some vertex v for which f(v)=2. The weight of a Roman dominating function is the value \(f(V)=\sum_{u\in V}f(u)\). The minimum weight of a Roman dominating function on a digraph D is called the Roman domination number of D, denoted by \(\gamma_R(D)\). Let \((V_0,V_1,V_2)\) be the ordered partition of V induced by f, where \(V_i=\{v\in V:f(v)=i\}\) for i=0,1,2. Note that there exists a 1-1 correspondence between the RDF f and the ordered partition \((V_0,V_1,V_2)\) of V. Thus, we will write \(f=(V_0,V_1,V_2)\). So, a function \(f=(V_0,V_1,V_2)\) is a Roman dominating function (RDF) if \(V_0\subseteq N^+[V_2]\). The weight of f is \(f(V)=\sum_{v\in V}f(v)=|V_1|+2\,|V_2|\), and we say that a RDF f is a \(\gamma_R\)-function if \(f(V)=\gamma_R(D)\). The Roman dominating function for graphs has been introduced by Cockayne et al. [1] and was motivated by an article in Scientific American by Ian Stewart entitled "Defend the Roman Empire" [11]. For more details on Roman domination and its variants, the reader can be referred to [2,3,8,9,12,13].

The concept of Roman dominating function for digraphs was introduced by Kamaraj and Jakkammal in [4], in their paper the authors gave the following upper bound for the parameter \(\gamma_R(D)\) and some others results.

\[\gamma_R(D) \le n - \Delta^+(D) + 1. \tag{1}\]

Later, in [4, 10] the authors gave some bounds and characterization of digraphs for small values of \(\gamma_R(D)\). In [7], the authors gave extremal oriented k-out-regular graphs with \(1 \leq k \leq n-1\), and tournaments attaining the upper bound in (1), also they showed that the problem of deciding whether an oriented graph D has \(\gamma_R(D) = n - \Delta^+(D) + 1\) is \(\mathcal{CO} - \mathcal{NP}\)-complete. In this paper, we characterize all oriented trees T satisfying \(\gamma_R(T) = n - \Delta^+(T) + 1\).

2. Characterization of Oriented Trees T with \(\gamma_R(T)=n-\Delta^+(T)+1\)

In this section, we give a characterization of oriented trees T with \(\gamma_R(T) = n - \Delta^+(T) + 1\). Recall that the known upper bound in (1) is given by Kamaraj and Jakkammal in [5].

Proposition 2.1. [5] If D is a digraph of order n, with maximum out-degree \(\Delta^+(D)\). Then

\[\gamma_R(D) \le n - \Delta^+(D) + 1.\]

Proposition 2.2. [10] If D is any digraph of order n, then \(\gamma_R(D) < n\) if and only if \(\Delta^+(D) \ge 2\).

Proposition 2.3. If T is any oriented tree of order \(n \ge 2\), then \(\gamma_R(T) = n\) if and only if \(\Delta^+(T) = 1\).

For the next result, let X be the set of vertices of an oriented tree T with out-degree 2, i.e., \(X = \{x \in V: d^+(x) = 2\}\).

Proposition 2.4. Let T be an oriented tree of order \(n \ge 2\) with maximum out-degree \(\Delta^+(T)\) and X be a set of vertices of out-degree 2. Then \(\gamma_R(T) = n - 1\) if and only if \(\Delta^+(T) = 2\), in addition if \(|X| \ge 2\) then X has an unique vertex, say z satisfies \(N_T^+[x] \cap N_T^+[y] = \{z\}\), for every pair of vertices x, y in X and x or y may be z (see Figure 1).

Proof. Let T be an oriented tree of order \(n \geq 2\). Assume that \(\gamma_R(T) = n-1\), and suppose to the contrary that \(\Delta^+(T) \neq 2\). By Observation 2.3, \(\Delta^+(T) \geq 3\) and by Proposition 2.1, \(\gamma_R(T) \leq n-\Delta^+(T)+1\), a contradiction. Thus \(\Delta^+(T)=2\) and \(|X|\geq 1\). Now, assume to the contrary that \(|X|\geq 2\) and there exists at least two vertices, say x and y in \(X_2\) such that \(\left|N_T^+[x]\cap N_T^+[y]\right|\neq 1\). Since T is an oriented tree, \(N_T^+[x]\cap N_T^+[y]=\emptyset\). The function \(f=(V_0,V_1,V_2)\), where \(V_1=V_1\) and \(V_2=\{x,y\}\), is an RDF of T, so \(\gamma_R(T)\leq |V_1|+2\,|V_2|=n-2\), a contradiction.

Conversely. Let \(x \in X\) (in case \(z \in X\), x may be z). Clearly by construction of T that the function \(f = (N_T^+(x), V - N_T^+[x], \{x\})\) is a \(\gamma_R(T)\)-function with \(\gamma_R(T) = |V_1| + 2|V_2| = (n-3) + 2 = n-1\).

Figure 1. (a) T with \(z \notin X\). (b) T with \(z \in X\).

In [7], Ouldrabah et al. gave necessary conditions for digraphs D such that \(\gamma_R(D)=n-\Delta^+(D)+1\). Since we are interested in oriented trees, we state their results only for the class of oriented trees. From now, T will be an oriented tree of order n with \(\gamma_R(T)=n-\Delta^+(T)+1\), x will be a vertex of maximum out-degree \(\Delta^+(T)\geq 3\) and \(\overline{N}^+[x]=V(T)-N^+[x]\).

The next three Lemmas contain main structure properties on oriented tree T with \(\gamma_R(T) = n - \Delta^+(T) + 1\), which we will need in order to prove the main results.

Lemma 2.1. [7] Let T be an oriented tree of order n and let x be a vertex with maximum outdegree \(\Delta^+(T) \geq 3\). If \(\gamma_R(T) = n - \Delta^+(T) + 1\) then

• 1. every vertex in \(\overline{N}^+[x]\) has at most one out-neighbor in \(\langle \overline{N}^+[x] \rangle\), and
• 2. every vertex in \(N_T^+(x)\) has at most two out-neighbors in T.

Lemma 2.2. Let T be an oriented tree of order n and maximum out-degree \(\Delta^+(T) \geq 3\). If \(\gamma_R(T) = n - \Delta^+(T) + 1\) then T has a unique vertex with out-degree at least three.

Proof. Let T be an oriented tree of order n and maximum out-degree \(\Delta^+(T) \geq 3\). Suppose there are two vertices x and y in T with out-degree at least 3. Without loss of generality, we can assume that \(d^+(x) = \Delta^+(T)\). If \(y \in \overline{N}^+[x]\) since T is an oriented tree, then y has at least two outneighbors that are in \(\overline{N}^+[x]\), that is \(\left|N^+(y) \cap \overline{N}^+[x]\right| \geq 2\) a contradiction with Lemma 2.1. Thus y must be is in \(N^+(x)\). But in this case, since T is an oriented tree, y has at least three outneighbors vertices in \(\overline{N}^+[x]\), that is \(\left|N^+(y) \cap \overline{N}^+[x]\right| \geq 3\), again a contradiction with Lemma 2.1.

Define the following subsets:

\[Y = \{ y \in N^{+}(x) : d^{+}(y) = 2 \},\] \[Z = \{ z \in N^{-}(x) : d^{+}(z) = 2 \},\] \[U = \{ u \in \overline{N}^{+}[x] - Z : d^{+}(u) = 2 \}.\] (6)

It is clear that U, Y and Z form a partition of the set X. Also we define the two following subsets:

\[W = (N^{+}(x) - Y) \cap N^{+}(U),\] \[R = N^{+}(x) - (Y \cup W).\] (7)

For illustration, see the oriented tree T in Figure 2.

Lemma 2.3. Let T be an oriented tree of order n and maximum out-degree \(\Delta^+(T) \geq 3\). If \(\gamma_R(T) = n - \Delta^+(T) + 1\) then \(|R| \geq 1\), and in addition if |R| = 1 then \(Z = \emptyset\).

Proof. Let T be an oriented tree of order \(n \geq 2\) with \(\gamma_R(T) = n - \Delta^+(T) + 1\), and x a vertex of T satisfying \(d^+(x) = \Delta^+(T)\). From Lemma 2.1, we have \(d^+(v) \leq 2\) for every vertex v in T - x. If \(X = \emptyset\), then \(\Delta^+(\langle T - x \rangle) \leq 1\), and the condition is done. Assume now that \(X = Z \cup Y \cup U \neq \emptyset\). Since \(Y \cup W \subseteq N^+(x)\) and T is an oriented tree we have

\[\Delta^{+}(T) = |N^{+}(x)| = |Y| + |W| + |R|,\]

and so

\[\begin{split} \left| N^{+} \left[ U \cup Y \right] \right| &= \left| N^{+} \left[ U \right] \right| + \left| N^{+} \left[ Y \right] \right| - \left| N^{+} \left( U \right) \cap Y \right| \\ &= 2 \left| U \right| + \left| W \right| + 3 \left| Y \right| \\ &= 2 \left| Y \right| + 2 \left| U \right| + \Delta^{+} (T) - \left| R \right|. \end{split}\]

First, we show that \(|R| \ge 1\). Assume to the contrary that \(R = \emptyset\), then

\[\Delta^{+}(T) = |N^{+}(x)| = |Y| + |W|.\]

The function \(f = (V_0, V_1, V_2)\), where

\[V_1 = V(T) - (N^+[U \cup Y])\] and \(V_2 = U \cup Y\)

is an RDF of T. Hence,

\[\gamma_R(T) \le |V_1| + 2|V_2|\] \[= |V(T)| - (2|Y| + 2|U| + \Delta^+(T)) + 2(|U| + |Y|)\] \[= n - \Delta^+(T),\]

a contradiction.

Now we must show that if |R|=1 then \(Z=\emptyset\). Suppose to the contrary that |R|=1 and \(Z\neq\emptyset\). Thus \(\Delta^+(T)=|Y|+|W|+1\). The function \(f=(V_0,V_1,V_2)\), where

\[V_{1} = V\left(T\right) - \left(N^{+}\left[U \cup Y \cup \{z\}\right]\right) \text{ and } V_{2} = U \cup Y \cup \{z\}\]

is an RDF of T where \(z \in Z\). Hence,

\[\gamma_{R}(T) \leq |V_{1}| + 2|V_{2}| = |V(T) - (N^{+}[U \cup Y \cup \{z\}])| + 2|U \cup Y \cup \{z\}| = |V(T)| - (2|Y| + 2|U| + \Delta^{+}(T) - |R| + |N^{+}[z]|) + 2(|U| + |Y| + |\{z\}|) = n - \Delta^{+}(T).\]

a contradiction.

In the sequel, we provide a characterization of trees T of order \(n \geq 2\) for which \(\gamma_R(T) = n - \Delta^+(T) + 1\). For this purpose, we define the following families of trees. Recall that \(X = \{x \in V : d^+(x) = 2\}\).

• \(\mathcal{F}_1\) the family of all oriented trees T with \(\Delta^+(T) = 1\).
• \(\mathcal{F}_2\) be the family of all oriented trees T with \(\Delta^+(T)=2\), and T has an unique vertex, say z satisfies \(X\subseteq N^-[z]\).
• \(\mathcal{F}_3\) be the family of all oriented trees T with \(\Delta^+(T) \geq 3\) satisfying the following conditions:
  • (a) T has a unique vertex x with out-degree at least three.
  • \((b) \ \ \Delta^{+}(\left\langle \overline{N}^{+}\left[x\right]\right\rangle) \leq 1, \text{ and every vertex in } N_{T}^{+}\left(x\right) \text{ has at most two out-neighbors in } T.\)
  • (c) \(|R| \ge 1\) and in addition if |R| = 1 then \(Z = \emptyset\).

We begin by giving a known result on digraph that will be useful to prove the main result.

Proposition 2.5. [5] Let \(f = (V_0, V_1, V_2)\) be any \(\gamma_R(D)\)-function of a digraph D. Then

• (a) If \(v \in V_1\), then \(N^-(v) \cap V_2 = \emptyset\);
• (b) Let \(H=D[V_0\cup V_2]\). Then each vertex \(v\in V_2\) with \(N^-(v)\cap V_2\neq\emptyset\), has at least two private neighbors with respect to \(V_2\) in the subdigraph H.

Figure 2. An example of oriented tree T which belongs to \(\mathcal{F}_3\). Note that R is not empty, and the set Z must be empty whenever |R| = 1.

We now are ready to give our main result.

Theorem 2.1. Let T be an oriented tree of order \(n \geq 2\) with maximum out-degree \(\Delta^+(T)\). Then

\[\gamma_{R}(T) = n - \Delta^{+}(T) + 1\] if and only if \(T \in \mathcal{F}_{1} \cup \mathcal{F}_{2} \cup \mathcal{F}_{3}\).

Proof. Let T be an oriented tree of order n ≥ 2 with maximum out-degree ∆⁺(T). If ∆⁺(T) = 1 or 2, then by Observation 2.3 and Proposition 2.4 γ^R (T) = n − ∆⁺ (T) + 1 if and only if T ∈ F¹ or T ∈ F2, respectively. Hence let ∆⁺(T) ≥ 3. Then from Lemmas 2.1, 2.2, and 2.3, T ∈ F3.

Conversely. Suppose T ∈ F3, by Condition (a) of the family F3, T has a unique vertex, say x with d + T (x) = ∆⁺(T) and ∆⁺( h N + [x] ∪ R i ) ≤ 1.

First we will show that there exists a γ^R (T)-function f with f(x) = 2. Suppose to the contrary that every γ^R (D)-function π, π(x) 6= 2. Let f = (V0, V1, V2) be a γR(T)-function, if there exists a vertex v in R such that f (v) = 0, then there exists a vertex w ∈ N + [x] such that w → v with f (w) = 2, and the function

\[g = (V_0 - \{v\}, V_1 \cup \{w, v\}, V_2 - \{w\})\]

is a γ^R (T)-function with g (v) = 1. And if there exists a vertex v in R such that f (v) = 2, then there exists a vertex w ∈ N + [x] such that v → w with f (w) = 0 and the function

\[h = (V_0 - \{w\}, V_1 \cup \{w, v\}, V_2 - \{v\})\]

is a γ^R (T)-function with h (v) = 1. So, we can suppose without loss of generality that f (v) = 1 for every vertex v in R. Since T ∈ F, we deduce from the Condition (c) that |R| ≥ 1. Since f (x) 6= 2, we distinguish tow cases:

Case 1. f (x) = 1. If |R| = 1, then the function

\[f' = (V_0 \cup R, V_1 - (R \cup \{x\}), V_2 \cup \{x\})\]

is γR-function with f 0 (x) = 2, a contradiction with the fact that every γ^R (D)-function π, π(x) 6= 2. If |R| ≥ 2, then f 0 is an RDF with f 0 (V ) < f (V ), a contradiction.

Case 2. f (x) = 0, then there exists a vertex u ∈ N − T (x), such that u → x with f (u) = 2, and since x → v with f (v) = 1, for every vertex v in E. We have three possibility:

Subcase 2.1. |R| = 1. Then

\[f' = (V_0 \cup R - \{x\}, (V_1 - R) \cup \{u\}, (V_2 - \{u\}) \cup \{x\})\]

is a γR(T)-function with f 0 (x) = 2, a contradiction.

Subcase 2.2. |R| ≥ 2 and Z = ∅. Then

\[f' = (V_0 \cup R - \{x\}, (V_1 - R) \cup \{u\}, (V_2 - \{u\}) \cup \{x\})\]

is a RDF with f 0 (V ) < f (V ), a contradiction.

Subcase 2.3. |R| ≥ 2 and Z 6= ∅. For the case u /∈ Z, like Subcase 2.2, we obtain a contradiction. Suppose now that u ∈ Z. If |R| = 2, then

\[f' = ((V_0 - \{x\}) \cup R, V_1 - R, V_2 \cup \{x\})\]

is a γR(T)-function with f 0 (x) = 2, a contradiction. And if |R| > 2, then f 0 is a RDF with f 0 (V ) < f (V ), a contradiction. Hence, there exists a γR(T)-function f (V ) = (V0, V1, V2) such V² contains x.

Now, we show that \(\gamma_R(T) = n - \Delta^+(T) + 1\). Suppose to the contrary

\[\gamma_R(T) < n - \Delta^+(T) + 1.\]

We have,

\[|V_1| + 2|V_2| < n - \Delta^+(T) + 1 = |V_0| + |V_1| + |V_2| - \Delta^+(T) + 1.\]

This implies that,

\[|V_0| \ge |V_2| + \Delta^+(T)\]. (2)

It follows from Proposition 2.5 item (a), \(N_D^+(x) \cap V_1 = \emptyset\). We define the two following subsets:

\[P=N_{D}^{+}\left( x\right) \cap V_{2} \text{ and } Q=N_{D}^{+}\left( x\right) \cap V_{0}.\]

Let |P| = p and |Q| = q, so \(p + q = \Delta^+(T)\). Since \(V_0 \subseteq N^+[V_2]\), clearly that \(|V_2| \ge 2\). Moreover, every vertex in \(V_2\), has at least an out-private neighbor in \(V_0\) with respect to V.

First, assume that \(P=\emptyset\). Since \(|V_2|\geq 2\) we can deduce from (2) that there exists at least two vertices, say u,v in \(V_0\) dominated by another vertex say x' in \(V_2\) other than x. i.e., \(x \nrightarrow u\), \(x \nrightarrow v\) and \(x' \Longrightarrow \{u,v\}\) which give \(\Delta^+(\left\langle \overline{N}^+ \left[x\right] \right\rangle) > 1\), a contradiction with the Condition (b) of the family \(\mathcal{F}_3\), so \(P \ne \emptyset\). On the one hand, by Proposition 2.5 item (b), each vertex in P has at least two out-private neighbors in \(V_0\) with respect to \(V_2\), and on the other hand, by Condition (b) of the family \(\mathcal{F}\) each vertex in \(N_T^+(x)\) has at most two out-neighbors in U, which implies that \(|N^+(P)\cap V_0|=2p\), since T is an oriented tree.

Now, we define the following subsets:

\[F = V_2 - (P \cup \{x\}) \text{ and } E = V_0 - (Q \cup (N^+(P) \cap V_0)).\] (3)

So,

\[|E| = |V_0| - |Q| - |N^+(P) \cap V_0| = |V_0| - q - 2p,\] (4)

It follows from (2), (3) and (4) that

\[|F| = |V_2| - (p+1) \le |V_0| - \Delta^+(T) - (p+1)\]
\[\le |E| + q + 2p - \Delta^+(T) - (p+1)\]
\[= |E| - 1 < |E|.\]

We have thus shown that |F| < |E|. But, since \(V_0 \subseteq N^+[V_2]\), thus \(F \neq \emptyset\) and \(E \subseteq N^+[F]\), which implies that there exists at least a vertex w in F such that \(\left|N_D^+(w) \cap E\right| \geq 2\), implying \(\Delta^+(\left<\overline{N}^+[x]\right>) \geq 2\), a contradiction with the Condition (b) of the family \(\mathcal{F}_3\). Hence, \(\gamma_R(D) = n - \Delta^+ + 1\).

3. References

[1] E.J. Cockayne, P.M.Dreyer Jr., S.M. Hedetniemi, and S. T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004), 11–22.

• [2] X. Chen, G. Hao, and Z. Xie, A note on Roman domination of digraphs, Discuss. Math. Graph Theory 39 (2019), 13–21.
• [3] E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math 23 (2009), 1575–1586.
• [4] M. Kamaraj and V. Hemalatha, Directed Roman domination in digraphs, International Journal of Combinatorial Graph Theory and Applications 4 (2011), 103–116.
• [5] M. Kamaraj, P. Jakkammal, Roman domination in digraphs. Submitted.
• [6] T. W. Haynes, S.T. Hedetniemi and M. A. Henning, Topics in domination in graphs, Springer (2020).
• [7] L. Ouldrabah, M. Blidia, and A. Bouchou, Extremal digraphs for an upper bound on the Roman domination number, J. Comb. Optim. 38 (2019), 667–679.
• [8] A. Poureidi, Total Roman domination for proper interval graphs. Electron. J. Graph Theory Appl. 8 (2) (2020), 401–413.
• [9] N.J. Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5 (2017), 1–6.
• [10] S.M. Sheikholeslami and L. Volkmann, The Romain Domination Number of a digraph, Acta Universitatis Apulenisis 27 (2011), 77–86.
• [11] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), 136–138.
• [12] S.M. Sheikholeslami and L. Volkmann, The signed Roman domatic number of a graph, Electron. J. Graph Theory Appl. 3 (1) (2015), 85–93.
• [13] E. Zhu and Z. Shao, Extremal problems on weak Roman domination number, Inform. Process. Lett. 138 (2018), 12–18.