Electronic Journal of Graph Theory and Applications

Doost Ali Mojdeh^a, Guoliang Hao^b, Iman Masoumi^c, Ali Parsian^c

damojdeh@umz.ac.ir, guoliang-hao@163.com, i_masoumi@yahoo.com, parsianali@yahoo.com

Given a simple graph G=(V,E) with maximum degree \(\Delta\). Let \((V_0,V_1,V_2)\) be an ordered partition of V, where \(V_i=\{v\in V:f(v)=i\}\) for i=0,1 and \(V_2=\{v\in V:f(v)\geq 2\}\). A function \(f:V\to\{0,1,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}\) is a strong Roman dominating function (StRDF) on G, if every \(v\in V_0\) has a neighbor \(w\in V_2\) and \(f(w)\geq 1+\lceil\frac{1}{2}|N(w)\cap V_0|\rceil\). A function \(f:V\to\{0,1,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}\) is a unique response strong Roman function (URStRF), if \(w\in V_0\), then \(|N(w)\cap V_2|\leq 1\) and \(w\in V_1\cup V_2\) implies that \(|N(w)\cap V_2|=0\). A function \(f:V\to\{0,1,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}\) is a unique response strong Roman dominating function (URStRDF) if it is both URStRF and StRDF. The unique response strong Roman domination number of G, denoted by \(u_{StR}(G)\), is the minimum weight of a unique response strong Roman domination function. In this paper we approach the problem of a Roman domination-type defensive strategy under multiple simultaneous attacks and begin with the study of several mathematical properties of this invariant. We obtain several bounds on such a parameter and give some realizability results for it. Moreover, for any tree T of order \(n\geq 3\) we prove the sharp bound \(u_{StR}(T)\leq \frac{8n}{0}\).

Keywords: strong Roman dominating function, unique response strong Roman (dominating) function

Mathematics Subject Classification: 05C69

DOI: 10.5614/ejgta.2021.9.2.18

Received: 8 December 2019, Revised: 10 April 2021, Accepted: 19 April 2021.

^&lt;sup>a</sup>Department of Mathematics, University of Mazandaran, Babolsar, Iran

^&lt;sup>b</sup>College of Science, East China University of Technology, Nanchang 330013, People's Republic of China

^&lt;sup>c</sup>Department of Mathematics, University of Tafresh, Tafresh, Iran

1. Introduction

The original study of Roman domination was motivated by the defense strategies of the Roman Empire during the reign of Emperor Constantine the Great, 274-337 A.D. Emperor Constantine had the requirement that an army or legion could be sent from its home to defend a neighboring location only if there was a second army which would stay and protect the home. Thus, there are two types of armies, stationary and mobile. Each vertex with no army must have a neighboring vertex with a mobile army. Stationary armies then dominate their own vertices, and a vertex with two armies is dominated by its stationary army, and its open neighborhood is dominated by the mobile armies. This part of history of the Roman Empire gave rise to the mathematical concept of Roman domination, as originally defined and discussed by Stewart [13] in 1999, and ReVelle and Rosing [11] in 2000. The defensive strategy of Roman domination is based on the fact that every place in which there is established a Roman legion (a label 1 in the Roman dominating function) is able to protect itself from external attacks; and that every unsecured (i.e., weak) place (a label 0) must have at least a stronger neighbor (a label 2). In that way, if an unsecured place is attacked, then the stronger neighbor can send it one of the two legions to defend it.

Two examples of Roman dominating functions are depicted in Figure 1.

Figure 1. Two Roman dominating functions.

Although these two functions (Figure 1) satisfy the conditions to be Roman dominating functions, they correspond to two very different real situations. The unique strong place 2 in Figure 1(b) must defend up to 8 unsecured locations from possible external attacks. However, in Figure 1(a), the task of defending the unsecured locations is divided between several strong locations. These observations have let us to pose the following question: how many weak locations/places can be defended by a strong location occupied by two legions? Taking into account that a strong place must leave one of its legions to defend itself, the situation depicted in Figure 1(b) does not seem to be an efficient defensive strategy: the Roman domination strategy fails against a multiple attack situation. If several simultaneous attacks to weak places occur, then a single stronger place will be not able to defend its neighbors efficiently. With this motivation in mind, in [1] Alvarez-Ruiz et al., introduced the concept of strong Roman dominating function. Then in other references such as [2, 7, 9, 15] the properties of this parameter have been studied.

Let G = (V, E) be a simple graph of order n = |V |, where V = V (G) and E = E(G). The open neighborhood of a vertex v ∈ V is the set N(v) = {u : uv ∈ E(G)}. If S is a subset of V , then N(S) = ∪x∈SN(x), N[S] = ∪x∈SN[x] and the subgraph induced by S in G is denoted G[S]. Let E^v be the set of all edges incident with a vertex v in G, that is, E^v = {uv ∈ E(G) : u ∈ N(v)}.

The degree of a vertex v is \(d_G(v) = deg(v) = |E_v|\). The minimum and maximum degree of G are denoted by \(\delta(G) = \delta\) and \(\Delta(G) = \Delta\). A star \(S_n\) of order \(n \geq 2\) is the complete bipartite graph \(K_{1,n-1}\). We call the center of a star to be a vertex of maximum degree. For two vertices u and v in a connected graph G, the distance d(u,v) between u and v is the length of a shortest (u,v)-path in G. The maximum distance among all pairs of vertices of G is the diameter of G, which is denoted by diam(G). For notations and terminologies, are not herein, see [14]. For a real-valued function \(f:V(G)\to\mathbb{R}\) and \(S\subseteq V(G)\), we define \(f(S)=\sum_{x\in S}f(x)\).

A set \(S \subseteq V\) is a dominating set of G if N[S] = V. The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set G. A set \(S \subseteq V(G)\) is a 2-packing set of G if for every pair of vertices \(x, y \in S\), \(N[x] \cap N[y] = \emptyset\). For more details on domination in graphs see [4], and for other domination parameters see [5, 8].

A Roman dominating function (RDF) on a graph G is a function \(f:V\to\{0,1,2\}\) such that every vertex u for which f(u)=0 is adjacent to at least one vertex v with f(v)=2. The weight of a Roman dominating function is the sum \(\omega(f)=\sum_{v\in V}f(v)\), and the minimum weight of an RDF of G is called the Roman domination number of G, denoted by \(\gamma_R(G)\), For further, see [6, 10].

From now on, if \(f:V\to\{0,1,2,\ldots\}\) is a function on G, then we let \(V_i=\{v\in V:f(v)=i\}\) for i=0,1 and \(V_2=\{v\in V:f(v)\geq 2\}\). A strong Roman dominating function (StRDF) on a graph G is a function \(f:V\to\{0,1,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}\) such that if \(v\in V_0\) for some \(v\in V\), then there exists a vertex \(w\in N(v)\) such that \(w\in V_2\) and \(f(w)\geq 1+\lceil\frac{1}{2}|N(w)\cap V_0|\rceil\). The minimum weight over all strong Roman dominating functions on G is called the strong Roman domination number of G, denoted by \(\gamma_{StR}(G)\). An independent strong Roman dominating function (IStRDF) of G is an StRDF such that the set of all vertices assigned positive values is independent. The independent strong Roman domination number \(i_{StR}(G)\) is the minimum weight of an IStRDF of G. an StRDF of minimum weight is called a \(\gamma_{StR}(G)\)-function and likewise \(i_{StR}(G)\)-function is defined. An example of an StRDF and an IStRDF can be seen on the graph in Figure 1 (b), by assigning a 5 to the vertex of maximum degree, a 1 to the vertex of degree 2 and a 0 to the remaining vertices.

In [12], Rubalcaba and Slater studied Roman domination influence of parameters in which the interest is in dominating each vertex exactly once. The authors [12] also introduced the concept of unique response Roman functions which we will adapt the definition for strong Roman functions as follows: A function \(f: V \to \{0, 1, \dots, \lceil \frac{\Delta}{2} \rceil + 1\}\) with the ordered partition \((V_0, V_1, V_2)\) of V is a unique response strong Roman function if \(w \in V_0\) then \(|N(w) \cap V_2| \le 1\) and \(w \in V_1 \cup V_2\) implies that \(|N(w) \cap V_2| = 0\). A function \(f: V \to \{0, 1, \dots, \lceil \frac{\Delta}{2} \rceil + 1\}\), is a unique response strong Roman dominating function, or just URStRDF, if it is a unique response strong Roman function and a strong Roman dominating function. The unique response strong Roman domination number, denoted by \(u_{StR}(G)\), is the minimum weight of a URStRDF of G.

It is worth mentioning that every graph has a unique response strong Roman dominating function since \((\emptyset, V(G), \emptyset)\) is such a function. Moreover, if \(f = (V_0, V_1, V_2)\) is a URStRDF on G, then \(V_2\) is a 2-packing set. In Figure 2, the black shaded pebble represents a stationary army and the white shaded pebble represents a traveling army. It is easy to check that an attack on any weak vertex of the graph will have three traveling army responding to the attacks.

Figure 2. A unique response strong Roman dominating function.

2. Preliminary results

In this section, we give some results on the unique response strong Roman domination number of graphs. Most of these results are straightforward and so we omit the proofs.

Observation 2.1. Let f = (V0, V1, V2) be an StRDF of graph G. If V² is independent and no edge of G joins V¹ and V2, then there is an IStRDF g of G such that ω(g) ≤ ω(f).

Observation 2.2. If G has an iStR(G)-function f = (V0, V1, V2) such that N(x) ∩ N(y) = ∅ for any pair x, y ∈ V2, then uStR(G) = iStR(G).

Observation 2.3. If G is a graph belonging to {Pn, Cn, Kn, Km,n}, then iStR(G) = uStR(G).

Observation 2.4. For \[n \geq 3\], \(u_{StR}(K_n) = \lceil \frac{n-1}{2} \rceil + 1\) and for \(n \geq m \geq 1\), \(u_{StR}(K_{n,m}) = \lceil \frac{n}{2} \rceil + m\).

It is known that γR(Pn) = γR(Cn) = d2n/3e . Clearly any RDF on paths and cycles is strong. Moreover, since paths and cycles have minimum RDF that are unique response, the following result then is immediate.

Proposition 2.1. For n ≥ 3, uStR(Pn) = uStR(Cn) = d2n/3e .

The next result shows that the difference between uStR(G) and γStR(G) can be arbitrarily large.

Proposition 2.2. For every integer k ≥ 2, there is a graph G = G^k such that uStR(G)−γStR(G) = k.

Proof. Let k ≥ 2 be an integer and let G^k be a double star in which every support vertex is of degree 2k + 1. It can be seen that uStR(G) = 3k + 2, while γStR(G) = 2k + 2.

3. Bounds

We provide in this section some upper and lower bounds for the unique response strong Roman domination number of a graph G in terms of maximum degree, minimum degree, the domination number, the diameter and the order of G. Obviously, every graph of order n, uStR(G) ≤ n, with equality if and only if each component of G has order at most two. Our next result improves the previous upper bound.

Theorem 3.1. For any graph G of order n, \(u_{StR}(G) \leq n - \lfloor \frac{\Delta}{2} \rfloor\), and furthermore, this bound is sharp for all graphs of order n with \(\Delta(G) = n - 1\).

Proof. Let v be a vertex of maximum degree, and consider the URStRDF f=(N(v),V(G)-N[v],v), where v is assigned the value \(\left\lceil\frac{\Delta}{2}\right\rceil+1\). Clearly, \(\omega(f)=n-\Delta+\left\lceil\frac{\Delta}{2}\right\rceil=n-\left\lfloor\frac{\Delta}{2}\right\rfloor\), implying the desired bound. The sharpness of the upper bound may be seen for all graph G of order n with \(\Delta(G)=n-1\). Since we have, \(n-\left\lfloor\frac{\Delta}{2}\right\rfloor=n-\left\lfloor\frac{n-1}{2}\right\rfloor=\left\lceil\frac{n-1}{2}\right\rceil+1\).

Corollary 3.1. If G is a graph of order n, then \(u_{StR}(G) = n\) if and only if \(\Delta(G) \leq 1\).

Proof. By pervious Theorem the proof is clear.

Theorem 3.2. Let G be a graph of order n and let v be a vertex of G with degree \(\Delta\). If \(u_{StR}(G) = n - \lfloor \frac{\Delta}{2} \rfloor\), then \(d(x) \leq 1\) for each \(x \in V(G) - N[N(v)]\).

Proof. Suppose, to the contrary, that there exists some vertex \(u \in V(G) - N[N(v)]\) such that \(d(u) \geq 2\). Then the function f defined by \(f(v) = \lceil \frac{\Delta}{2} \rceil + 1\), \(f(u) = \lceil \frac{d(u)}{2} \rceil + 1\), f(x) = 0 for \(x \in N(v) \cup N(u)\) and f(x) = 1 otherwise, is a URStRDF on G, and so

\[u_{StR}(G) \leq \left( \lceil \frac{\Delta}{2} \rceil + 1 \right) + \left( \lceil \frac{d(u)}{2} \rceil + 1 \right) + \left( n - |N[v]| - |N[u]| \right)\] \[= \left( \lceil \frac{\Delta}{2} \rceil + 1 \right) + \left( \lceil \frac{d(u)}{2} \rceil + 1 \right) + \left( n - \Delta - d(u) - 2 \right)\] \[= n - \lfloor \frac{\Delta}{2} \rfloor - \lfloor \frac{d(u)}{2} \rfloor\] \[\leq n - \lfloor \frac{\Delta}{2} \rfloor - 1,\]

a contradiction.

We remark that the condition of Theorem 3.2 is not sufficient. For example, let \(t \ge s-1 \ge 3\) and let G be the graph of order \(n \ (= s+t)\) obtained from a complete graph \(K_s\) and a star \(S_t\) with center v by deleting a edge \(u_1u_2\) of \(K_s\) and joining v to \(u_1\). Then the function f defined by \(f(u_2) = \lceil \frac{s-2}{2} \rceil + 1\), \(f(v) = \lceil \frac{t}{2} \rceil + 1\) and f(x) = 0 otherwise, is a URStRDF on G, and so

\[u_{StR}(G) \leq (\lceil \frac{s-2}{2} \rceil + 1) + (\lceil \frac{t}{2} \rceil + 1)\] \[= \lceil \frac{s}{2} \rceil + \lceil \frac{t}{2} \rceil + 1\] \[= s + t - \lfloor \frac{s}{2} \rfloor - \lfloor \frac{t}{2} \rfloor + 1\] \[= n - \lfloor \frac{s}{2} \rfloor - \lfloor \frac{\Delta}{2} \rfloor + 1\] \[\leq n - \lfloor \frac{\Delta}{2} \rfloor - 1.\]

Lemma 3.1. Let G be a graph with maximum degree \(\Delta\) and let \(f = (V_0, V_1, V_2, \dots, V_{\lceil \frac{\Delta}{2} \rceil + 1})\) where \(V_i = \{v \in V : f(v) = i, \ 0 \le i \le \lceil \frac{\Delta}{2} \rceil + 1\}\) be a \(u_{StR}(G)\)-function. Then

\[|V_2| + 2|V_3| + \ldots + \lceil \frac{\Delta}{2} \rceil |V_{\lceil \frac{\Delta}{2} \rceil + 1}| \ge \lceil \frac{\Delta}{2} \rceil.\]

Proof. Let x be a vertex with \(deg(x)=\Delta\). If \(f(x)=\lceil\frac{\Delta}{2}\rceil+1\), then the inequality is clear. Now we assume that \(f(x)\in\{0,1\}\). Let f(x)=1 and let \(V_x^1=V_1\cap N(x)\). Then \(N(x)-V_x^1\subseteq V_0\). If \(N(x)-V_x^1=\emptyset\) and \(N(N(x))-\{x\}=\{v_1,v_2,\ldots,v_k\}\), then \(f(N[x])=\Delta+1\) and \(f(N(N(x))-\{x\})\cup(\bigcup_{i=1}^kN(v_i)-N(x))\geq k\). Therefore in this case f is not a minimum URStRDF respected to \(f(x)=\lceil\frac{\Delta}{2}\rceil+1\). Now assume that \(N(x)-V_x^1\neq\emptyset\). Let \(N(x)\cap V_0=N_1\cup N_2\cup\ldots\cup N_k\), where \(N_i\) is the vertices in \(N(x)\cap V_0\) with common neighbor \(v_i\) and \(v_i\neq x\) for \(1\leq i\leq k\).

Let \(N(v_i)-N(x)=\emptyset\). Then \(f(v_i)\geq \lceil\frac{|N_i|}{2}\rceil+1\) and so \(f(\{x\}\cup V_x^1\cup N(N(x)\cap V_0))\geq 1+|V_x^1|+k+\sum_{i=1}^k\lceil\frac{|N_i|}{2}\rceil\). We show that f is not a minimum unique respond strong Roman dominating function, respected to when \(f(x)=\lceil\frac{\Delta}{2}\rceil+1\), f(N(x))=0 and \(f(N(N(x))-\{x\})=k\). It is well known that \(\Delta\leq\sum_{i=1}^k|N_i|+|V_x^1|\). Therefore \(\lceil\frac{\Delta}{2}\rceil\leq\sum_{i=1}^k\lceil\frac{|N_i|}{2}\rceil+\lceil\frac{|V_x^1|}{2}\rceil\) and \(1+\lceil\frac{\Delta}{2}\rceil+k\leq 1+\sum_{i=1}^k\lceil\frac{|N_i|}{2}\rceil+k+\lceil\frac{|V_x^1|}{2}\rceil\leq 1+\sum_{i=1}^k\lceil\frac{|N_i|}{2}\rceil+k+|V_x^1|\). Thus, if we assign \(f(x)=\lceil\frac{\Delta}{2}\rceil+1\), f(N(x))=0 and f(u)=1 for the vertex in N(N(x))-x, then \(f(\{x\}\cup N(x)\cup (N(x))-\{x\}))\leq k+\lceil\frac{\Delta}{2}\rceil+1\leq 1+\sum_{i=1}^k\lceil\frac{|N_i|}{2}\rceil+k+|V_x^1|\). Let \(N(v_i)-N(x)\neq\emptyset\) for some \(1\leq i\leq k\). Let \(M_i=N(v_i)-N(x)\). It is well known

Let \(N(v_i)-N(x)\neq\emptyset\) for some \(1\leq i\leq k\). Let \(M_i=N(v_i)-N(x)\). It is well known that: If f(x)=1 and \(f(N(x)-V_x^1)=0\), then we should have \(f(v_i)=\lceil\frac{|N_i|+|M_i|}{2}\rceil+1\) and \(f(N(v_i)-N(x))=0\). If \(f(x)=\lceil\frac{\Delta}{2}\rceil+1\) and f(N(x))=0, then \(f(v_i)=1\) and for every vertex \(u\in N(v_i)-N(x)\), \(f(u)\leq 1\). Assume that we use the URStRDF f where \(f(x)\in\{0,1\}\). There are two cases.

Case 1. Let \(|V_x^1| \leq \sum_{i=1}^k |M_i|\). Then \(\sum_{i=1}^k (|N_i| + |M_i|) \geq \sum_{i=1}^k |N_i| + |V_x^1| \geq \Delta\) and so \(\sum_{i=1}^k \lceil \frac{|N_i| + |M_i|}{2} \rceil \geq \lceil \frac{\Delta}{2} \rceil\). So the result holds.

Case 2. Let \(|V_x^1| \ge \sum_{i=1}^k |M_i|\). Since \(\sum_{i=1}^k |N_i| + |V_x^1| \ge \Delta\), hence \(\sum_{i=1}^k \frac{|N_i|}{2} + \sum_{i=1}^k \frac{|M_i|}{2} + |V_x^1| \ge \frac{\Delta}{2} + \sum_{i=1}^k |M_i|\). Therefore \(\sum_{i=1}^k \lceil \frac{|N_i| + |M_i|}{2} \rceil + k + 1 + |V_x^1| \ge \lceil \frac{\Delta}{2} \rceil + 1 + k + \sum_{i=1}^k |M_i|\). This means that in this case f is not a minimum URStRDF, respected to when \(f(x) = \lceil \frac{\Delta}{2} \rceil + 1\), f(N(x)) = 0 and \(f(N(N(x)) - \{x\}) = k\) and \(f(\bigcup_{i=1}^k N(v_i) - N(x)) \le \sum_{i=1}^k |M_i|\).

Let f(x)=0. Then at least one vertex of N(x) is in \(V_2\cup\ldots\cup V_{\lceil\frac{\Delta}{2}\rceil+1}\). Now using similar proof in case of f(x)=1 we can show that \(f(N(x)\cup N(N(x)))\geq \lceil\frac{\Delta}{2}\rceil\). These show that, we can always use the URStRDF function that assigns the vertex x with \(deg(x)=\Delta\) the value \(\lceil\frac{\Delta}{2}\rceil+1\). Therefore, in any case

\[|V_2| + 2|V_3| + \dots + \lceil \frac{\Delta}{2} \rceil |V_{\lceil \frac{\Delta}{2} \rceil + 1}| \ge \lceil \frac{\Delta}{2} \rceil,\]

as desired. \(\Box\)

Theorem 3.3. If G is a connected graph with \(\Delta(G) \geq 1\), then \(u_{StR}(G) \geq \gamma(G) + \lceil \frac{\Delta}{2} \rceil\), and this bound is sharp.

Proof. Clearly, \(n \ge 2\) since \(\Delta(G) \ge 1\). If n = 2, then \(\gamma(G) = 1\) and \(u_{StR}(G) = 2 = \gamma(G) + 1 = \gamma(G) + \lceil \frac{\Delta}{2} \rceil\). Hence, let \(n \ge 3\). Then \(\Delta \ge 2\), since G is connected. Consider an \(u_{StR}(G)\)-function

\(f=(V_0,V_1,V_2,\ldots,V_{\lceil\frac{\Delta}{2}\rceil+1}), \text{ where } V_i=\{v\in V: f(v)=i\} \text{ for every } i\in\{0,1,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}.\) By Lemma 3.1, \(|V_2|+2|V_3|+\cdots+\lceil\frac{\Delta}{2}\rceil|V_{\lceil\frac{\Delta}{2}\rceil+1}|\geq \lceil\frac{\Delta}{2}\rceil.\) Therefore

\[u_{StR}(G) = |V_1| + 2|V_2| + \dots + (\lceil \frac{\Delta}{2} \rceil + 1)|V_{\lceil \frac{\Delta}{2} \rceil + 1}| =\] \[|V_1| + |V_2| + \dots + |V_{\lceil \frac{\Delta}{2} \rceil + 1}| + |V_2| + 2|V_3| + \dots + \lceil \frac{\Delta}{2} \rceil |V_{\lceil \frac{\Delta}{2} \rceil + 1}|\] \[\geq \gamma(G) + \lceil \frac{\Delta}{2} \rceil.\]

For sharpness, let G be a star \(K_{1,n-1}\) or complete graph \(K_n\) where \(n \geq 2\). Then \(\gamma(G) = 1\) and \(\lceil \frac{\Delta}{2} \rceil = \lceil \frac{n-1}{2} \rceil\) and \(u_{StR}(G) = 1 + \lceil \frac{n-1}{2} \rceil = \gamma(G) + \lceil \frac{\Delta}{2} \rceil\).

The next result gives a characterization of connected graphs attaining equality in the lower bound of Theorem 3.3.

Theorem 3.4. Let G be a connected graph of order n with \(\Delta(G) \geq 1\). Then \(u_{StR}(G) = \gamma(G) + \lceil \frac{\Delta}{2} \rceil\) if and only if G has a vertex of degree \(n - \gamma(G)\).

Proof. Suppose that G has a vertex v with degree \(deg(v) = n - \gamma(G)\). By Theorem 3.1,

\[u_{StR}(G) \le n - \Delta(G) + \lceil \frac{\Delta}{2} \rceil \le n - (n - \gamma(G)) + \lceil \frac{\Delta}{2} \rceil\]\[= \gamma(G) + \lceil \frac{\Delta}{2} \rceil,\]

and the equality follows from Theorem 3.3.

Conversely, assume that \(u_{StR}(G)=\gamma(G)+\lceil\frac{\Delta}{2}\rceil\) and let \(f=(V_0,V_1,V_2,\ldots,V_{\lceil\frac{\Delta}{2}\rceil+1})\) be a \(u_{StR}\)-function for G. It follows that

\[\gamma(G) + \lceil \frac{\Delta}{2} \rceil = u_{StR}(G) = |V_1| + 2|V_2| + \dots + (\lceil \frac{\Delta}{2} \rceil + 1)|V_{\lceil \frac{\Delta}{2} \rceil + 1}| = |V_1| + |V_2| + \dots + |V_{\lceil \frac{\Delta}{2} \rceil + 1}| + |V_2| + 2|V_3| + \dots + \lceil \frac{\Delta}{2} \rceil |V_{\lceil \frac{\Delta}{2} \rceil + 1}| \ge \gamma(G) + |V_2| + 2|V_3| + \dots + \lceil \frac{\Delta}{2} \rceil |V_{\lceil \frac{\Delta}{2} \rceil + 1}|,\]

and therefore \(\gamma(G)=|V_1|+|V_2|+\cdots+|V_{\lceil\frac{\Delta}{2}\rceil+1}|\) and \(|V_2|+2|V_3|+\cdots+(\lceil\frac{\Delta}{2}\rceil)(|V_{\lceil\frac{\Delta}{2}\rceil+1}|)=\lceil\frac{\Delta}{2}\rceil.\) Now using Lemma 3.1 and its proof, we have \(|V_{\lceil\frac{\Delta}{2}\rceil+1}|>0\). Therefore we deduce \(|V_2|=|V_3|=\cdots=|V_{\lceil\frac{\Delta}{2}\rceil}|=0\) and \(|V_{\lceil\frac{\Delta}{2}\rceil+1}|=1\). Consequently, \(\gamma(G)+\lceil\frac{\Delta}{2}\rceil=u_{StR}(G)=|V_1|+(\lceil\frac{\Delta}{2}\rceil+1),\) and so \(|V_1|=\gamma(G)-1\). Hence \(|V_0|=n-\gamma(G).\) Since every vertex of \(V_0\) is adjacent to the unique vertex of \(V_{\lceil\frac{\Delta}{2}\rceil+1},\) say v, and no vertex of \(V_1\) is adjacent to v, we deduce that \(deg(v)=n-\gamma(G).\)

Theorem 3.5. Let G be a graph of order n. If G has a \(u_{StR}\)-function \(f = (V_0, V_1, V_2, \dots, V_{\lceil \frac{\Delta}{2} \rceil + 1})\) such that \(V_1 = \emptyset\), then \(u_{StR}(G) \leq \frac{(\lceil \frac{\Delta}{2} \rceil + 1)n}{\Delta + 1}\), and this bound is sharp.

Proof. Let \(f=(V_0,V_1,V_2,\ldots,V_{\lceil\frac{\Delta}{2}\rceil+1})\) be a \(u_{StR}\)-function of G with \(V_1=\emptyset\). Then for every vertex \(v\in V-V_0\), we have \(f(x)\in V_i\) for \(i\geq 2\). Hence, if we have \(x\in V\) such that \(deg(x)=\Delta\), we may at most assign label \(\lceil\frac{\Delta}{2}\rceil+1\) to the vertex x and label 0 to its neighbors. Thus we have \(f(N[x])=\lceil\frac{\Delta}{2}\rceil+1\). Therefore we conclude \(u_{StR}(G)\leq \frac{\lceil\frac{\Delta}{2}\rceil+1}{\Delta+1}n\). The sharpness of the bound may be seen for the star \(K_{1,n-1}\) where \(n\geq 2\). Clearly, \(u_{StR}(G)=\lceil\frac{n-1}{2}\rceil+1=\frac{\lceil\frac{\Delta}{2}\rceil+1}{\Delta+1}n\). Also the sharpness of the bound may be seen for the other family of graphs as follows. Let \(G_1\) and \(G_2\) be stars \(K_{1,2m}\) where \(m\geq 1\) such that G is obtained from \(G_1\) and \(G_2\) where one of leaves of \(G_1\) is adjacent to one of leaves of \(G_2\). Then n=|V(G)|=4m+2, \(u_{StR}(G)=2(m+1)\) and \(\Delta(G)=2m\). Therefore \(u_{StR}(G)=2(m+1)=\frac{(\lceil\frac{\Delta}{2}\rceil+1)n}{\Delta+1}\).

Theorem 3.6. Let G be a graph of order n with \(\Delta \geq 1\). If \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) is a \(u_{StR}\)-function and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\), then \(u_{StR}(G) \geq \frac{kn}{\Delta + 1}\), and this bound is sharp.

Proof. Let \(f=(V_0,V_1,V_2,\ldots,V_{\lceil\frac{\Delta}{2}\rceil+1})\) be a \(u_{StR}\)-function of G. Since \(|V_0|\leq \Delta(|V_k|+\cdots+|V_{\lceil\frac{\Delta}{2}\rceil+1}|)\) and \(|V_1|\leq \frac{\Delta}{k}|V_1|\), we have

\[kn = k(|V_0| + |V_1| + |V_k| + \dots + |V_{\lceil \frac{\Delta}{2} \rceil + 1}|)\] \[\leq k(\Delta |V_k| + \dots + \Delta |V_{\lceil \frac{\Delta}{2} \rceil + 1}| + \frac{\Delta}{k} |V_1| + |V_k| + \dots + |V_{\lceil \frac{\Delta}{2} \rceil + 1}|)\] \[= \Delta |V_1| + (\Delta + 1)(k|V_k| + \dots + k|V_{\lceil \frac{\Delta}{2} \rceil + 1}|)\] \[= (\Delta + 1)(\frac{\Delta}{\Delta + 1} |V_1| + k|V_k| + \dots + k|V_{\lceil \frac{\Delta}{2} \rceil + 1}|).\]

Moreover, since \(\frac{\Delta}{\Delta+1}|V_1|+k|V_k|+\cdots+k|V_{\lceil\frac{\Delta}{2}\rceil+1}|\leq u_{StR}(G)\), we deduce that \(kn\leq (\Delta+1)u_{StR}(G)\) yielding the desired bound. The sharpness of the bound may be seen for the star \(K_{1,n-1}\) with \(n\geq 2\). Clearly, \(k=\lceil\frac{n-1}{2}\rceil+1\) and \(u_{StR}(G)=\lceil\frac{n-1}{2}\rceil+1=\frac{kn}{\Delta+1}\).

Theorem 3.7. If G is a nontrivial connected graph, then

\[u_{StR}(G) = \min\{\sum_{i=1}^{\lceil \frac{\Delta}{2} \rceil} (i+1) |S_i| + |V(G) - N[S]| : S = \bigcup S_i \text{ is a 2-packing set} \}.\]

Proof. Let \(f = (V_0, \dots, V_{\lceil \frac{\Delta}{2} \rceil + 1})\) be a \(u_{StR}\)-function of G. Since \(V - (V_0 \cup V_1)\) is a 2-packing, let \(S_i = V_{i+1}, \ 1 \leq i \leq \lceil \frac{\Delta}{2} \rceil\). Observe that \(V_1 = V - N[S]\). It follows that \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) is a 2-packing\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\).

On the other hand, let \(D=V_2\cup\cdots\cup V_{\lceil\frac{\Delta}{2}\rceil+1}\) be a 2-packing of G such that \(\sum_{i=1}^{\lceil\frac{\Delta}{2}\rceil+1}i\,|V_i|+|V(G)-N[D]|\) is minimum. Then f=(N(D),V(G)-N[D],D) is a URStRDF, implying that \(u_{StR}(G)\leq w(f)\) and the equality follows.

Theorem 3.8. Let G be a connected graph with \(diam(G) \ge 3\), then

\[u_{StR}(G) \le n - \lfloor \frac{\operatorname{diam}(G) - 1}{3} \rfloor.\]

Furthermore, this bound is sharp for paths \(P_{3k+2}\) with \(k \geq 0\).

Proof. Let \(\operatorname{diam}(G) = d = 3m + t\) for some integers \(m \geq 1\) and \(t \in \{0, 1, 2\}\). Let \(P = y_0y_1 \dots y_d\) be a diametral path in G, and let \(f: V(P) \to \{0, 1, 2\}\) be a URStRDF defined on P by assigning a 2 to every vertex in \(V_2 = \{y_0, y_3, \dots, y_{3m}\}\), a 0 to \(N(V_2)\) and a 1 to the remaining vertices of P. Note that \(V_2\) is a 2-packing set of P as well as of G. Define now a function \(g: V \to \{0, 1, \dots, \lceil \frac{\Delta}{2} \rceil + 1\}\) by g(x) = f(x) for \(x \in V(P)\) and g(x) = 1 otherwise. We also define a function \(h: V \to \{0, 1, \dots, \lceil \frac{\Delta}{2} \rceil + 1\}\) by \(h(y_i) = \lceil \frac{d_G(v_i)}{2} \rceil + 1\) for every \(i \in \{0, 3, \dots, 3m\}\), h(x) = 0 for every \(x \in N(y_i)\) such that \(i \in \{0, 3, \dots, 3m\}\) and h(y) = g(y) for any remaining vertex y. Clearly, h is a URStRDF on G and we have \(\omega(h) \le \omega(g) \le f(P) + n - (Diam(G) + 1)\). Thus \(\omega(h) \le \frac{2(Diam(G)+1)+2}{3} + n - Diam(G) - 1\). Finally, by simple calculations we have \(u_{StR}(G) \le \omega(h) \le \frac{3n - \operatorname{diam}(G)+1}{3} = n - \frac{\operatorname{diam}(G)-1}{3} \le n - \lfloor \frac{\operatorname{diam}(G)-1}{3} \rfloor\). For sharpness, let G be a path \(P_{3k+2}\) with \(k \ge 0\). Then \(u_{StR}(G) = \gamma_{StR}(G) = \lceil \frac{2n}{3} \rceil = \lceil \frac{2(3k+2)}{3} \rceil = 2k + 2\). On the other hand, we have n = 3k + 2, \(\operatorname{diam}(G) = 3k + 1\). Thus, \(n - \lfloor \frac{\operatorname{diam}(G)-1}{3} \rfloor = 3k + 2 - \lfloor \frac{3k+1-1}{3} \rfloor = 2k + 2\).

Recall that a vertex \(v \in S\) is said to have a private neighbor with respect to the set S if there exists a vertex \(w \in N(v) \cap (V-S)\) for which \(N(w) \cap S = \{v\}\). Let \(\operatorname{pn}[v,S]\) denote the set of private neighbors of v with respect to the set S.

Theorem 3.9. If G is a graph with \(\Delta(G) \geq 3\), then

\[u_{StR}(G) \le i_{StR}(G) + \lceil \frac{i_{StR}(G) - \lceil \frac{\Delta}{2} \rceil - 1}{\lceil \frac{\Delta}{2} \rceil + 1} (\Delta(G) - \lceil \frac{\Delta}{2} \rceil - 1) \rceil.\]

Proof. Let G be a graph with \(\Delta(G) \geq 3\). If \(i_{StR}(G) \geq u_{StR}(G)\), then since \(i_{StR}(G) \geq \lceil \frac{\Delta}{2} \rceil + 1\), the inequality holds. Hence, we assume that \(i_{StR}(G) < u_{StR}(G)\), and let \(f = (V_0^f, V_1^f, V_2^f)\) be an \(i_{StR}(G)\)-function. Then there exist two vertices \(x_1\) and \(y_1 \in V_2^f\) such that \(N(x_1) \cap N(y_1) \neq \emptyset\), for otherwise, by Observation 2.2, \(i_{StR}(G) = u_{StR}(G)\), a contradiction. Without loss of generality, we assume that \(d_G(x_1) \leq d_G(y_1)\). It follows that the function \(f_1\) defined by

\[f_1 = (V_0^{f_1}, V_1^{f_1}, V_2^{f_1}) = (V_0^f \setminus \operatorname{pn}(x_1, V_2^f), V_1^f \cup \operatorname{pn}(x_1, V_2^f) \cup \{x_1\}, V_2^f \setminus x_1).\]

is an StRDF such that \(V_2^{f_1}\) is independent, where no edge of G joins \(V_1^{f_1}\) and \(V_2^{f_1}\). By Observation 2.1, there is an IStRDF \(g_1 = (V_0^{g_1}, V_1^{g_1}, V_2^{g_1})\) of G with weight at most \(\omega(f_1)\). Now using the facts that \(\left|\operatorname{pn}(x_1, V_2^f)\right| \leq d_G(x_1) - 1\) (since \(N(x_1) \cap N(y_1) \neq \emptyset\)) and \(d_G(x_1) - \lceil \frac{d_G(x_1)}{2} \rceil - 1 \leq 1\)

\(\Delta(G) - \lceil \frac{\Delta}{2} \rceil - 1\), we obtain

\[\omega(f_1) \leq w(f) - \left( \lceil \frac{d_G(x_1)}{2} \rceil + 1 \right) + 1 + \left| \operatorname{pn}(x_1, V_2^f) \right|\] \[\leq i_{StR}(G) + d_G(x_1) - \left\lceil \frac{d_G(x_1)}{2} \right\rceil - 1\] \[\leq i_{StR}(G) + \left( \lceil \frac{d_G(x_1)}{2} \rceil + 1 \right) \frac{\left( \Delta(G) - \lceil \frac{\Delta}{2} \rceil - 1 \right)}{\lceil \frac{\Delta}{2} \rceil + 1}.\]

Thereafter, if \(V_2^{g_1}\) is not a 2-packing, then there must exist two vertices \(x_2\) and \(y_2 \in V_2^{g_1}\) with \(N(x_2) \cap N(y_2) \neq \emptyset\). As above, we can define a function \(f_2\) and so on. Clearly, with this process we can get an IStRDF \(g_k = (V_0^{g_k}, V_1^{g_k}, V_2^{g_k})\) of G for some integer \(k \leq |V_2^f| - 1\) such that \(V_2^{g_k}\) is a 2-packing set yielding \(u_{StR}(G) \leq i_{StR}(G) + |V_{\lceil \frac{d_G(x_1)}{2} \rceil + 1}|(\lceil \frac{d_G(x_1)}{2} \rceil + 1) \frac{\Delta(G) - \lceil \frac{\Delta}{2} \rceil - 1}{\lceil \frac{\Delta}{2} \rceil + 1} + \cdots + (|V_{\lceil \frac{d_G(x_k)}{2} \rceil + 1}| - 1)(\lceil \frac{d_G(x_k)}{2} \rceil + 1) \frac{\Delta(G) - \lceil \frac{\Delta}{2} \rceil - 1}{\lceil \frac{\Delta}{2} \rceil + 1}\). Moreover, since

\[|V_{\lceil \frac{d_G(x_1)}{2} \rceil + 1}|(\lceil \frac{d_G(x_1)}{2} \rceil + 1) + \dots + |V_{\lceil \frac{d_G(x_k)}{2} \rceil + 1}|(\lceil \frac{d_G(x_k)}{2} \rceil + 1) \le i_{StR}(G)\]

we deduced that

\[u_{StR}(G) \le i_{StR}(G) + \lceil \frac{i_{StR}(G) - \lceil \frac{\Delta}{2} \rceil - 1}{\lceil \frac{\Delta}{2} \rceil + 1} (\Delta(G) - \lceil \frac{\Delta}{2} \rceil - 1) \rceil.\]

This completes the proof.

The following corollaries are immediate consequences of Theorem 3.9 and Observation 2.2.

Corollary 3.2. If G is a graph with maximum degree three, then \(u_{StR}(G) \leq i_{StR}(G)\).

Corollary 3.3. If G is a cubic graph, then \(u_{StR}(G) \leq i_{StR}(G)\).

4. URStRDF of trees

In this section, we show that for any tree T of order \(n \geq 3\), \(u_{StR}(T) \leq \frac{8n}{9}\) and then we characterize some extremal trees which attain this upper bound. We now need to introduce some terminologies and notations. A vertex of degree one is called a leaf and its neighbor is called a support vertex. We denote the set of all leaves adjacent to support vertex v, by \(L_v\). For \(r, s \geq 1\), a double star S(r,s) is a tree with exactly two vertices that are not leaves, with one adjacent to r leaves and the other to s leaves. A rooted graph is a graph in which one vertex is labeled in a special way so as to distinguish it from other vertices. The special vertex is called the root of the graph. For a vertex v in a rooted tree T, let C(v) denote the set of children of v, D(v) denote the set of descendants of v and \(D[v] = D(v) \bigcup \{v\}\). Also, we denote the depth of v, by depth(v) that is the most length distance from v to a vertex in D(v). The maximal subtree at v is the subtree of T induced by \(D(v) \bigcup \{v\}\), and is denoted by \(T_v\).

Now, we present a result on the unique response strong Roman domination number of double stars. Let T=S(r,s) be a double star. For s=r=2, \(u_{StR}(T)=5=\frac{5n}{6}\). Here we characterise the \(u_{StR}(T)\) of any double star T.

Observation 4.1. Let r, s be integers with \(1 \le r \le s\) and \(s \ne 2\) or \(r \ne 2\). Then any double star T = S(r,s) of order n = r + s + 2, \(u_{StR}(T) \leq \lfloor \frac{4n}{5} \rfloor\) and equality holds if and only if one of the following cases is satisfied.

• (i) r = s and \(s \in \{1, 3, 4, 5, 6, 7, 8, 10, 12\}\), or
• (ii) r = s 1 and \(s \in \{2, 3, 4, 5, 6, 8, 10\}\), or
• (iii) r = s 2 and \(s \in \{3, 4, 6, 8\}\), or
• (iv) r = s 3 and \(s \in \{4, 6\}\).

Proof. Let u, v be two support vertices of T such that deg(u) = r + 1 and deg(v) = s + 1. We define URStRDF function f on V(T) as follows: \(f(v) = 1 + \lceil \frac{s+1}{2} \rceil\), f(u) = 0, f(x) = 0 for every vertex x adjacent to v and f(y) = 1 for every vertex y adjacent to u. Then \(\omega(f) = 1 + \left\lceil \frac{s+1}{2} \right\rceil + r\).

Now there are two cases. Let s be odd. Then \(\omega(f) = \frac{s+2r+3}{2} \le \lfloor \frac{4}{5}(s+r+2) \rfloor\). Let s be even and \(s \ne 2\), \(r \ne 2\). Then \(\omega(f) = \frac{s+2r+4}{2} \le \lfloor \frac{4}{5}(s+r+2) \rfloor\). A simple calculation shows that each condition of (i)-(iv) yields \(u_{StR}(S(r,s)) = \lfloor \frac{4n}{5} \rfloor\). Now suppose that for \(T = \frac{1}{5}\)S(r,s), we have \(u_{StR}(S(r,s)) = \lfloor \frac{4n}{5} \rfloor\). We consider some cases.

Case 1. Let r = s.

Let s be an odd integers. Then \(\frac{s+2r+3}{2}=u_{StR}(S(r,s))=\lfloor\frac{4n}{5}\rfloor=\lfloor\frac{4(r+s+2)}{5}\rfloor\). Therefore \(\frac{3s+3}{2}=\lfloor\frac{8s+8}{5}\rfloor=s+1+\lfloor\frac{3s+3}{5}\rfloor\) and then \(\frac{s+1}{2}=\lfloor\frac{3s+3}{5}\rfloor=\frac{s+1}{2}+\lfloor\frac{s+1}{10}\rfloor\). Thus \(\lfloor\frac{s+1}{10}\rfloor=0\) and s is one of the odd integers in \(\{1, 3, 5, 7\}\).

Let s be an even integer. Then \(\frac{3s+4}{2} = \lfloor \frac{4}{5}(2s+2) \rfloor\). Therefore \(\frac{3s+4}{2} = \lfloor \frac{s-4}{10} \rfloor + \frac{3s+4}{2}\). Thus \(\lfloor \frac{s-4}{10} \rfloor = 0\) and s is one of the even integers in \(\{4, 6, 8, 10, 12\}\).

Case 2. Let r = s - 1.

Let s be an odd integer. Then \(\frac{3s+1}{2} = \lfloor \frac{4(2s+1)}{5} \rfloor = s + \lfloor \frac{s+1}{2} + \frac{s+3}{10} \rfloor\). Thus \(\lfloor \frac{s+3}{10} \rfloor = 0\) and \(s \in \{3, 5\}\)since the value 1 for s is not acceptable.

Let r=s-1. Let s be an even integer. Then \(\frac{3s+2}{2}=\lfloor\frac{4(2s+1)}{5}\rfloor=s+\lfloor\frac{s+2}{2}+\frac{s-2}{10}\rfloor\). Thus \(\lfloor\frac{s-2}{10}\rfloor=0\)and \(s \in \{2, 4, 6, 8, 10\}\).

Case 3. Let r = s - 2.

Let s be an odd integer. Then \(\frac{3s-1}{2}=\lfloor\frac{8s}{5}\rfloor=s+\lfloor\frac{s-1}{2}+\frac{s+5}{10}\rfloor\). Thus \(\lfloor\frac{s+5}{10}\rfloor=0\) and \(s\in\{3\}\) since the value 1 for s is not acceptable.

Let r=s-2. Let s be an even integer. Then \(\frac{3s}{2}=\lfloor\frac{8s}{5}\rfloor=\frac{3s}{2}+\lfloor\frac{s}{10}\rfloor\). Thus \(\lfloor\frac{s}{10}\rfloor=0\) and \(s \in \{4, 6, 8\}\) since the value 1 for s is not acceptable.

Case 4. Let r = s - 3.

Let s be an odd integer. Then \(\frac{3s-3}{2} = \lfloor \frac{8s-4}{5} \rfloor = \frac{3s-3}{2} + \lfloor \frac{s+7}{10} \rfloor\). Thus \(\lfloor \frac{s+7}{10} \rfloor = 0\) and s cannot achieve any odd integer, since the value 1 for s is not acceptable

Let r=s-3. Let s be an even integer. Then \(\frac{3s-2}{2}=\lfloor\frac{8s}{5}\rfloor=\frac{3s-2}{2}+\lfloor\frac{s+2}{10}\rfloor\). Thus \(\lfloor\frac{s+2}{10}\rfloor=0\) and \(s \in \{4, 6\}\) since the value 2 for s is not acceptable.

Let r=s-k where \(4 \le k \le s-1\). In this case \(u_{StR}(S(r,s))=\frac{3s+3-2k}{2}\) for odd s and

\(u_{StR}(S(r,s)) = \frac{3s+4-2k}{2} \text{ for even } s. \text{ On the other hand } \left\lfloor \frac{4}{5}(n) \right\rfloor = \left\lfloor \frac{4}{5}(2s-k+2) \right\rfloor = \left\lfloor \frac{8s-4k+8}{5} \right\rfloor.\) Let s be an odd integer. Then \(\left\lfloor \frac{8s-4k+8}{5} \right\rfloor = \left\lfloor \frac{s+1+2k}{10} \right\rfloor + \frac{3s+3-2k}{2}\). Since \(k \geq 4\), \(\left\lfloor \frac{s+1+2k}{10} \right\rfloor \geq 1\). Let s be an even integer. Then \(\left\lfloor \frac{8s-4k+8}{5} \right\rfloor = \left\lfloor \frac{s-4+2k}{10} \right\rfloor + \frac{3s+4-2k}{2}\). Since \(k \geq 4\), and value 4 for s is not acceptable \(\left\lfloor \frac{s-4+2k}{10} \right\rfloor \geq 1\).

Therefore, for any value of s other than of value stated in the parts (i)-(iv) \(u_{StR}(S(r,s)) < \lfloor \frac{4}{5}(n) \rfloor\)where n = r + s + 2.

The proof of Observation 4.1, \(u_{StR}(S(r,s))\), and definition of \(i_{StR}(G)\) we deduce:

Corollary 4.1. \(i_{StR}(S(r,s)) = u_{StR}(S(r,s))\) for positive integers r, s where \(r \leq s\).

The following sharp bound is the main result in this section, where we bound the unique response strong Roman domination number of trees in terms of their orders.

Theorem 4.1. If T is a tree of order \(n \geq 3\), then \(u_{StR}(T) \leq \frac{8n}{9}\).

Proof. By induction on the order of T we prove the theorem. Clearly, theorem holds for all trees of order \(n \leq 5\). Let \(n \geq 6\) and for every tree T of order at least 3 and less than n the result is true. Let T be a tree of order \(n \geq 6\). If Diam(T) = 2, then T is a star, which yields \(u_{StR}(T) = 1 + \left\lceil \frac{n-1}{2} \right\rceil < \frac{8n}{9}\). If Diam(T) = 3, then T is a double star and the result follows from Observation 4.1. Thus, we can assume that \(Diam(T) \geq 4\). But in Observation 9 we have seen for the infinite number of natural numbers n and the infinite number of trees T of order n, \(u_{StR}(T) \leq \frac{8n}{9}\). Now we will continue to prove the Theorem for every tree T such that |T| = n, with the help of backward induction. Suppose for any tree T of order \(n \geq 3\), we have \(i_{StR}(T) \leq \frac{8n}{9}\). Now let T' be an arbitrary tree of order n = 1. Also, we take the diametral path \(P = v_0 v_1 \dots v_l\) of among diametral paths in T' so that \(t = deg_T(v_1)\) is the maximum. We put \(s = deg(v_2)\). Now we have four cases.

Case 1. t is an even number.

In this case we put \(T=T'\bigcup\{u\}\) such that \(u\in N(v_1)\). Under the assumption of induction, for this tree T, there exists a URStRDF f such that \(\omega(f)<\frac{8n}{9}\). But we must have f(u)=0 or f(u)=1. If f(u)=1 then we have \(f(v_1)=0\) or \(f(v_1)=1\). If \(f(v_1)=0\), then for any \(x\in L_{v_1}\), f(x)=1 and \(f(v_2)=\left\lceil\frac{s}{2}\right\rceil+1\). So if we define the URStRDF f' on T' by f'(x)=f(x) for every vertex \(x\in V(T')\), then we conclude \(\omega(f')=\omega(f)-1<\frac{8n}{9}-1=\frac{8n-9}{9}=\frac{8(n-1)-1}{9}<\frac{8(n-1)}{9}\). If \(f(v_1)=1\) then similarly, the assertion of the proposition is proved.

Now if f(u)=0, then we must have \(f(v_1)=\lceil\frac{t+1}{2}\rceil+1\). So we define URStRDF f' on T' by \(f'(v_1)=\lceil\frac{t}{2}\rceil+1\) and for the other vertices of z, f'(z)=f(z). Since t+1 is an odd number then we have \(\omega(f')=\omega(f)-1<\frac{8(n-1)}{9}\). Similarly, if the vertices \(v_2,v_3,\ldots,v_{l-1}\) are of an even degree, the proof is complete in the same way. Therefore, it can be assumed that the vertices of \(v_1,v_2,v_3,\ldots,v_{l-1}\) are of odd degrees.

Case 2. t is an odd number and \(s \ge 3\). Then we have two following cases.

Case 2.1. The vertex \(v_2\) has an adjacent vertex, such as u, which is either a leaf or an end-support of even degree. If \(u \in N(v_2)\) is a leaf, then we put \(T = T' \bigcup \{w'\}\) such that \(w' \in N(u)\) is a leaf. If f(w') = 0, then we must have f(u) = 2, \(f(v_2) = 0\), \(f(v_1) = 1\) and for any \(x \in N(v_1)\), f(x) = 1. Now we define URStRDF f' on T' by f'(u) = 1, \(f'(v_2) = 0\), \(f'(v_1) = \lceil \frac{t}{2} \rceil + 1\), for any \(x \in N(v_1)\), f'(x) = 0 and for the other vertices of \(z \in V(T')\), f'(z) = f(z). So, we have \(\omega(f') \leq \omega(f) - 1 < \frac{8(n-1)}{9}\). If f(w') = 1, then f(u) = 0 or f(u) = 1. If f(u) = 0, then \(f(v_2) = \lceil \frac{s}{2} \rceil + 1\). So, we can define URStRDF f' on f'(x) = f(x) which we have \(\omega(f') \leq \omega(f) - 1 < \frac{8(n-1)}{9}\). If f(u) = 1, then similarly, the assertion of the proposition is proved. If f(u) = 1, f(u) = 1, then we must have \(f(u) = \frac{degu+1}{2} \rceil + 1\). Now we define the function f(x) = 1 by letting f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) = 1, f(x) =

any \(z \in V(T')\). Hence, we have \(\omega(f') \le \omega(g) - 1 \le \omega(f) - 1 < \frac{8(n-1)}{9}\). If f(w') = 1, then similarly, the assertion of the proposition is proved.

Case 2.2. The vertex \(v_2\) has not an adjacent vertex which is either a leaf or an end-support of even degree. Therefore, each neighboring end-support from vertex \(v_2\) will be of an odd degree. We have two following cases.

Case 2.2.1. t>s. We put \(T=T'\bigcup\{u,u',u''\}\) such that \(P_3=u'uu''\) is a three vertex path and the vertex u is connected to vertex \(v_2\). If \(f(v_1)=\left\lceil\frac{t}{2}\right\rceil+1\) then we have \(f(v_2)=0\) and f(u)=f(u')=f(u'')=1. Now we define the function f' on T' by f'(z)=f(z). Hence, we have \(\omega(f')=\omega(f)-3<\frac{8(n+2)}{9}-3=\frac{8n+16-27}{9}=\frac{8n-11}{9}=\frac{8(n-1)-3}{9}<\frac{8(n-1)}{9}\). If \(f(v_1)=0\), then \(f(v_2)=0\) or \(f(v_2)=1\) or \(f(v_2)=\left\lceil\frac{s}{2}\right\rceil+1\). If \(f(v_2)=1\), then there exists \(w\in L_{v_1}\) such that f(w)=2. In this case we must have f(u)=f(u')=f(u'')=1. Hence, similar to the previous one, the result is achieved. If \(f(v_2)=0\), then there exist \(w\in L_{v_1}\) and \(x\in N(v_2)\) such that f(w)=2 and \(f(x)=\left\lceil\frac{degx}{2}\right\rceil+1\). Since, \(s+1\geq 4\) then we can suppose \(x\neq u\). Thus, we have f(u)=f(u')=f(u'')=1. Hence, similar to the previous one, the result is achieved. Finally, if \(f(v_2)=\left\lceil\frac{s+1}{2}\right\rceil+1\), then we have \(f(v_1)=0=f(v_3)\) and for any \(x\in L_{v_1}\), f(x)=1. Now we define URStRDF g on T by letting \(g(v_2)=0\), \(g(v_1)=\left\lceil\frac{t}{2}\right\rceil+1\), \(g(v_3)=1\) and for any \(y\in L_{v_1}\) and for any \(z\in N(v_2)-\left\{v_1,v_3\right\}\) g(y)=0, g(z)=1. Clearly, we have \(\omega(g)\leq \omega(f)<\frac{8(n+2)}{9}\). Now we define URStRDF f' on T' by f'(z)=g(z). Thus, we have \(\omega(f')=\omega(f)-3<\frac{8(n+2)}{9}-3=\frac{8n+16-27}{9}=\frac{8n-11}{9}=\frac{8(n-1)-3}{9}<\frac{8(n-1)}{9}\). Case 2.2.2. \(t\leq s\). We put \(degv_3=s'\). If \(t\geq s'\), then s'< s. In this case, we suppose that

Case 2.2.2. \(t \le s\). We put \(degv_3 = s'\). If \(t \ge s'\), then s' < s. In this case, we suppose that \(T = T' \bigcup \{u, u', u''\}\) such that \(P_3 = u'uu''\) is a three vertex path and the vertex u is connected to vertex \(v_3\). Now we continue the argument in the same way as before. But if t < s', then we put \(T' = T \bigcup \{u\}\) such that \(u \in N(v_1)\). Thus, \(f(v_1) = 0\) or \(f(v_1) = 1\). Now we continue the argument in the same way as before.

This completes the proof. \(\Box\)

Theorem 4.2. If T is a tree of order \(n \geq 3\), then, \(i_{StR}(T) \leq \frac{8n}{9}\).

Proof. We prove this theorem by induction on \(n \geq 3\). Clearly, the theorem holds for all trees of order \(n \leq 5\). By the inductive hypothesis, let \(n \geq 6\) and suppose that for every tree T of order at least 3 and less than n the result is true. Let T be a tree of order \(n \geq 6\). If Diam(T) = 2, then T is a star, which yields \(i_{StR}(T) = 1 + \left \lceil \frac{n-1}{2} \right \rceil < \frac{8n}{9}\). If Diam(T) = 3, then T is a double star and the result follows from pervious lemma. Thus, we can assume that \(Diam(T) \geq 4\). For a subtree T' with \(n' \geq 3\), the induction hypothesis yields a IStRDF f' of T' with weight at most \(\frac{8n'}{9}\). We shall find a subtree T' such that adding a bit more weight to f' will yield a small enough IStRDF f for T. We take the diametral path \(P = v_0 v_1 \dots v_l\) of among diametral paths in T so that \(t = deg_T(v_1)\) is the maximum. Also, suppose that among paths with this property we choose a path such that \(|L_{v_2}|\) is as large as possible. Root T at \(v_l\).

If t=3, \(s=deg(v_2)\), s=3 and the vertex \(v_2\) has only one neighboring support vertex of degree three, for example u, except for vertex \(v_1\). We put \(T'=T-T_{v_2}\). Therefore, the induction hypothesis yields a IStRDF f' of T' weight at most \(\frac{8n'}{9}\). Now we define a function f on T by \(f(u)=f(v_1)=3\), for any \(x\in N(v_1)\), f(x)=0, for every \(y\in N(u)\), f(y)=0 and for every other vertex z, f(z)=f'(z). So, we have \(\omega(f)\leq \omega(f')+6<\frac{8n'}{9}+6\leq \frac{8(n-7)}{9}+6=\frac{8n-2}{9}<\frac{8n}{9}\).

Thus, for every \(n \geq 3\) and for any tree T of order n such that the tree T applies to the conditions of the previous state, we have \(i_{StR}(T) \leq \frac{8n}{9}\). Now we will continue to prove the theorem for every tree T such that |T| = n, with the help of backward induction. Suppose for any tree T of order \(n \geq 3\), we have \(i_{StR}(T) \leq \frac{8n}{9}\). Now let T' be an arbitrary tree of order n-1. Also, we take the diametral path \(P = v_0v_1\ldots v_l\) of among diametral paths in T' so that \(t = deg_T(v_1)\) is the maximum. We put \(s = deg(v_2)\). Now we have four cases.

Case 1. t is an even number. In this case we put \(T = T' \bigcup \{u\}\) such that \(u \in N(v_1)\). Under the assumption of induction, for this tree T, there exists a IStRDF f such that \(\omega(f) < \frac{8n}{9}\). But we must have f(u) = 0 or f(u) = 1. If f(u) = 1, then we have \(f(v_1) = 0\) and for any \(x \in L_{v_1}\), f(x) = 1 and \(f(v_2) = \left\lceil \frac{s}{2} \right\rceil + 1\). So if we define the IStRDF f' on T' by f'(x) = f(x) for every vertex \(x \in V(T')\), then we conclude \(\omega(f') = \omega(f) - 1 < \frac{8n}{9} - 1 = \frac{8n-9}{9} = \frac{8(n-1)-1}{9} < \frac{8(n-1)}{9}\). Now if f(u) = 0, then we must have \(f(v_1) = \left\lceil \frac{t+1}{2} \right\rceil + 1\). So we define IStRDF f' on T' by \(f'(v_1) = \left\lceil \frac{t}{2} \right\rceil + 1\) and for the other vertices of z, f'(z) = f(z). Since t + 1 is an odd number then we have \(\omega(f') = \omega(f) - 1 < \frac{8(n-1)}{9}\). Similarly, if the vertices \(v_2, v_3, \ldots, v_{l-1}\) are of an even degree, the proof is complete in the same way. Therefore, it can be assumed that the vertices of \(v_1, v_2, v_3, \ldots, v_{l-1}\) are of odd degrees.

Case 2. t is an odd number and \(s \geq 3\). Then we have two following cases. Case 2.1. The vertex \(v_2\) has an adjacent vertex, such as u, which is either a leaf or an end-support of even degree. If \(u \in N(v_2)\) is a leaf, then we put \(T = T' \bigcup \{w'\}\) such that \(w' \in N(u)\) is a leaf. If \(f(v_2) = 0\), then we must have f(u) = 2, f(w') = 0 and \(f(v_1) = \lceil \frac{t}{2} \rceil + 1\). Now we define IStRDF f' on T' by f'(u) = 1 and for the other vertices of \(x \in V(T')\), f'(x) = f(x). So, we have \(\omega(f') = \omega(f) - 1 < \frac{8(n-1)}{9}\). If \(f(v_2) = \lceil \frac{s}{2} \rceil + 1\), then we must have f(u) = 0 and f(w') = 1. We define IStRDF f' on T' by f'(u) = 0 and for the other vertices of \(x \in V(T')\), f'(x) = f(x). So, we have \(\omega(f') = \omega(f) - 1 < \frac{8(n-1)}{9}\). If \(u \in N(v_2)\) is an end-support of even degree, then we put \(T = T' \bigcup \{w'\}\) such that \(w' \in N(u)\) is a leaf. Now the proof is complete in the same way.

Case 2.2. The vertex \(v_2\) has not an adjacent vertex which is either a leaf or an end-support of even degree. Therefore, each neighboring end-support from vertex \(v_2\) will be of an odd degree. We have two following cases.

Case 2.2.1. \(t \geq 5\). We put \(T = T' \bigcup \{u, u'\}\) such that \(u, u' \in N(v_0)\) are leaves. If \(f(v_0) = 0\), then we must have \(f(v_1) = \lceil \frac{t}{2} \rceil + 1\) and f(u) = f(u') = 0. Now we define IStRDF f' on T' by f'(x) = f(x) for every \(x \in V(T')\). So, we have \(\omega(f') = \omega(f) - 2 < \frac{8(n+1)}{9} - 2 = \frac{8(n-1)-2}{9} < \frac{8n}{9}\). If \(f(v_0) = 3\) the we must have \(f(v_l) = f(u) = f(u') = 0\) and for any vertex \(x \in L_{v_1}\), f(x) = 0. Now if \(f(v_2) = \lceil \frac{s}{2} \rceil + 1\), then we define a function f' on T' by \(f'(v_0) = 1\) and for any other vertices \(z \in V(T')\) f'(z) = f(z). Thus, we have \(\omega(f') = \omega(f) - 2 \le \frac{8(n+1)}{9} - 2 < \frac{8n}{9}\). But if \(f(v_2) = 0\), then we define a function g on T by \(g(v_1) = \lceil \frac{t}{2} \rceil + 1\), for any vertex \(x \in N(v_1)\), g(x) = 0 and g(u) = g(u') = 1. So, we have \(\omega(g) \le \omega(f)\). Now we define a function f' on T' by f'(x) = g(x). Then we have \(\omega(f') = \omega(g) - 2 < \frac{8n}{9}\).

Case 2.2.2. t=3 and the vertex \(v_2\) has at least two neighboring vertices, which are end-support vertices of degree three. We denote those vertices by \(u_1,\ldots,u_{k-1}\). Now we consider a subtree T'' such that \(T''\simeq T_{v_2}\). We put \(T=T'\bigcup T''\) such that if w is the central vertex of T'', then w is connected by an edge to the vertex \(v_1\). So, for every function f' on T' we have \(\omega(f')\leq \omega(f)-3k<\frac{8(n-1)+3k+1)}{9}-3k=\frac{8n-3k}{9}<\frac{8(n-1)-3k+8}{9}<\frac{8(n-1)}{9}\). This completes the

proof. \(\Box\)

Following we show that this bound is sharp. Let G be a labeled graph on n vertices and let H be a rooted graph with root v. The rooted product graph \(G \circ_v H\) is the graph obtained from G and n copies of H, say \(H_1 \cdots H_n\), by identifying the root of the copy \(H_i\) of H with the \(i^{th}\) vertex of G, Godsil and McKay [3]. If H is a vertex transitive graph, then \(G \circ_v H\) does not depend on the choice of v, up to isomorphism. In such a case we will just write \(G \circ H\).

Let \(S(K_{1,4})\) (the star \(K_{1,4}\) with all its edges subdivided) be rooted in its center v and let \(F_m^p\) consist of all the rooted product graphs \(To_vS(K_{1,4})\), where T is any tree on \(m \ge 2\) vertices (see Figure 3 for an example).

Figure 3. A member of \(F_4^p\).

Theorem 4.3. Let T be an n-vertex tree. If \(T \in F_m^p\) and \(m \ge 2\), then \(u_{StR}(T) = \frac{8n}{9}\).

Proof. Firstly, we notice that if the graph \(H=S(K_{1,4})\) is an induced subgraph H of G, and its noncentral vertices have no neighbors outside H in G, then any URStRDF must put total weight at least 8 on the vertices of H. For the case of trees \(T\in F_m^p\), \(m\geq 2\), they contain m disjoint induced subgraphs isomorphic to \(S(K_{1,4})\) satisfying the situation mentioned above. So, \(u_{StR}(T)\geq \frac{16n}{18}=\frac{8n}{9}\) for each \(T\in F_m^p\), \(m\geq 2\). But since every tree \(T\in F_m^p\) has a vertex partition of \(m\geq 2\) sets including such subgraphs, a weight of at least 16 is needed on every set of such partition. Moreover, it is easy to find a \(u_{StR}\)-function of weight \(\frac{8n}{9}\), which leads to the equality. \(\square\)

Acknowledgement

Thanks are due to the anonymous referees for useful comments and valuable suggestions. This work was supported by National Natural Science Foundation of China (Nos. 12061007 and 11861011).

References

• [1] M.P. Alvarez-Ruiz, T. Mediavilla-Gradolph, S.M. Sheikholeslami, J.C. Valenzuela-Tripodoro, and I.G. Yero, On the strong Roman domination number of graphs, Discrete Appl. Math. 231 (2017) 44–59.
• [2] X.G. Chen and M.Y Sohn, Trees with equal strong Roman domination number and Roman domination number, Bull. Korean Math. Soc. (56) (2019), 31–44.
• [3] C.D. Godsil and B.D. McKay, A new graph product and its spectrum, Bull. Aust. Math. Soc. 18 (1) (1978) 21–28.

• [4] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. , New York (1998).
• [5] S.M. Hosseini Moghaddam, D.A. Mojdeh, B. Samadi, and L. Volkman, On the signed 2 independence number of graphs, Electron. J. Graph Theory Appl. 5 (1) (2017), 36–42.
• [6] N. Jafari Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5 (1) (2017), 1–6.
• [7] A. Mahmoodi, S. Nazari-Moghaddam, and A. Behmaram, Some results on the strong Roman domination number of graphs, Mathematics Interdisciplinary Research (5) (2020), 259–277.
• [8] D.A. Mojdeh, S.R. Musawi, and E. Nazari Kiashi, On the distance domination number of bipartite graphs, Electron. J. Graph Theory Appl. 8 (2) (2020), 353–364.
• [9] S. Nazari-Moghaddam, M. Soroudi, S.M. Sheikholeslami, and I.G. Yero, On the total and strong version for Roman dominating functions in graphs, Aequationes Math. 95 (2021) 215- 236.
• [10] A. Poureidi, Total Roman domination for proper interval graphs, Electron. J. Graph Theory Appl., 8 (2) (2020), 401–413.
• [11] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (7) (2000), 585–594.
• [12] R. Rubalcaba and P.J. Slater, Roman dominating influence parameters, Discrete Math. 307 (24) (2007), 3194–3200.
• [13] I. Stewart, Defend the Roman Empire!, Scientific American. 281 (6) (1999), 136–139.
• [14] D. B. West, Introduction to Graph Theory, Second Edition, Prentice-Hall, Upper Saddle River, NJ, (2001).
• [15] J. Xu and Z. Wang, Note on strong Roman domination in graphs, Appl. Math. Sci. 12 (2018), 535–541.