Article Search
eISSN 0454-8124
pISSN 1225-6951

### Article

KYUNGPOOK Math. J. 2019; 59(3): 515-523

Published online September 23, 2019

### Strong Roman Domination in Grid Graphs

Xue-Gang Chen, Moo Young Sohn∗

Department of Mathematics, North China Electric Power University, Beijing 102206, China
e-mail : gxcxdm@163.com
Department of Mathematics, Changwon National University, Changwon 51140, Korea
e-mail : mysohn@changwon.ac.kr

Received: January 2, 2019; Revised: September 3, 2019; Accepted: September 19, 2019

Consider a graph G of order n and maximum degree ∆. Let f:V(G){0,1,,Δ2+1} be a function that labels the vertices of G. Let B0 = {vV (G) : f(v) = 0}. The function f is a strong Roman dominating function for G if every vB0 has a neighbor w such that f(w)1+12|N(w)B0|. In this paper, we study the bounds on strong Roman domination numbers of the Cartesian product PmPk of paths Pm and paths Pk. We compute the exact values for the strong Roman domination number of the Cartesian product P2Pk and P3Pk. We also show that the strong Roman domination number of the Cartesian product P4Pk is between 13(8kk8+1 and 8k3 for k ≥ 8, and that both bounds are sharp bounds.

Keywords: Roman domination number, strong Roman domination number, grid.

Graph theory terminology not presented here can be found in [1]. Let G = (V, E) be a graph with |V| = n. The degree, neighborhood and closed neighborhood of a vertex v in the graph G are denoted by dG(v), NG(v) and NG[v] = NG(v) ∪ {v}, respectively. If the graph G is clear from context, we simply write d(v), N(v) and N[v], respectively. The minimum degree and maximum degree of the graph G are denoted by δ(G) and ∆(G), respectively. The diameter diam(G) of a connected graph G is the maximum distance between two vertices of G. The graph induced by SV is denoted by G[S]. A path on n vertices is denoted by Pn.

For two graphs G1 and G2, the Cartesian product G1G2 is the graph with vertex set V (G1) × V (G2), where vertex (u1, v1) is adjacent to vertex (u2, v2) if and only if either u1 = u2 and v1v2E(G2) or v1 = v2 and u1u2E(G1). G = PmPk is called a grid graph.

Let {vij|1 ≤ im, 1 ≤ jk} be the vertex set of G = PmPk so that the subgraph induced by ℛ i = {vi1, vi2, …, vik} is isomorphic to the path Pk for each 1 ≤ im and the subgraph induced by is isomorphic to the path Pm for each 1 ≤ jk.

A set SV in a graph G is called a dominating set if N[S] = V. The domination number γ(G) equals the minimum cardinality of a dominating set in G. A dominating set of G with cardinality γ(G) is called a γ-set of G.

Let f : V → {0, 1, 2} be a function having the property that for every vertex vV with f(v) = 0, there exists a neighbor uN(v) with f(u) = 2. Such a function is called a Roman dominating function. The weight of a Roman dominating function is the sum $f(V)=∑v∈Vf(v)$. The minimum weight of a Roman dominating function on G is called the Roman domination number of G and is denoted γR(G). Roman domination was defined and discussed by Stewart [4] in 1999. It was developed by ReVelle and Rosing [3] in 2000 and Cockayne et al. [2] in 2004. In order to deal with multiple simultaneous attacks, Álvarez-Ruiz et al. [1] in 2017 initiated the study of a new parameter related to Roman dominating function, which is called strong Roman domination.

Consider a graph G of order n and maximum degree ∆. Let $f:V(G)→{0,1,…,⌈Δ2⌉+1}$ be a function that labels the vertices of G. Let B0 = {vV : f(v) = 0}. Then f is a strong Roman dominating function for G, if every vB0 has a neighbor w, such that $f(w)≥1+⌈12|N(w)∩B0|⌉$. The weight of a strong Roman dominating function is the sum $f(V)=∑v∈Vf(v)$. The minimum weight of a strong Roman dominating function on G is called the strong Roman domination number of G and is denoted γStR(G). A strong Roman dominating function of G with weight γStR(G) is called a γStR-function of G. For any SV, define $f(S)=∑v∈Sf(v)$. Let f be a γStR-function of G. Let B2 = {vV : f(v) ≥2}. For any vB0, there exists a vertex uB2 such that vuE(G). We say that v is dominated by u or by B2. If f is a strong Roman dominating function of G, then every vertex in B0 is dominated by some vertex in B2.

In this paper, we study the bounds on strong Roman domination numbers of the Cartesian product PmPk of paths Pm and paths Pk. Exact values for the strong Roman domination number of the Cartesian product P2Pk and P3Pk are found, and it is shown that for the strong Roman domination number of the Cartesian product P4Pk this number is between $⌈13(8k−⌊k8⌋+1⌉$ and $⌈8k3⌉$ for k ≥ 8, and both bounds are sharp bounds.

### Bounds of Strong Roman Domination Number of Pm□Pk

In this section, we present upper and lower bounds on the strong Roman domination number of the Cartesian product of paths Pm and paths Pk.

### Observation 2.1

For any positive integers m, k such that k ≡ 0(mod 3), $γStR(Pm□Pk)≤2mk3$.

Proof

Let G = PmPk, where k = 3t for a positive integer t. Let V2 = {vij|1 ≤ im, j = 3l − 1, 1 ≤ lt}, V1 = ∅ and V0 = V (G) (V1V2). Clearly, (V0, V1, V2) is a partition of V (G). Define f on V (G) by f(v) = i for any vVi, where 0 ≤ i ≤ 2. It is obvious that f is a strong Roman dominating function of G. Therefore, $γStR(G)≤|f(V(G))|=2mk3$.

### Observation 2.2

For any positive integers m, k such that k ≡ 1(mod 3), $γStR(Pm□Pk)≤m(2k+1)3$.

Proof

Let G = PmPk, where k = 3t + 1 for a positive integer t. Let V2 = {vij|1 ≤ im, j = 3l − 1, 1 ≤ lt}, V1 = {vik|1 ≤ im} and V0 = V (G) (V1V2). Clearly, (V0, V1, V2) is a partition of V (G). Define f on V (G) by f(v) = i for any vVi, where 0 ≤ i ≤ 2. It is obvious that f is a strong Roman dominating function of G. Therefore, $γStR(G)≤|f(V(G))|=m(2k+1)3$.

### Observation 2.3

For any positive integers m, k such that k ≡ 2(mod 3), then$γStR(Pm□Pk)≤{m(4k+1)6if m≡0 (mod 2)m(4k+1)+36if m≡1 (mod 2).$

Proof

Let G = PmPk, where k = 3t + 2 for a positive integer t. Suppose m ≡ 0 (mod 2). Let $V2={vij|1≤i≤m,j=3l−1,1≤l≤t}∪{vjk|j=4l+1,0≤l≤⌊m−14⌋}∪{vjk|j=4l,1≤l≤⌊m4⌋}$, $V1={vj(k−1)|j=4l+2,0≤l≤⌊m−14⌋}∪{vj(k−1)|j=4l−1,1≤l≤⌊m4⌋}$ and V0 = V (G) (V1V2). Clearly, (V0, V1, V2) is a partition of V (G). Define f on V (G) by f(v) = i for any vVi, where 0 ≤ i ≤ 2. It is obvious that f is a strong Roman dominating function of G. Therefore, $γStR(G)≤f(V(G))=m(4k+1)6$.

Suppose that m ≡ 1 (mod 2). Let $V2={vij|1≤i≤m,j=3l−1,1≤l≤t}∪{vjk|j=4l+1,0≤l≤⌊m−24⌋}∪{vjk|j=4l,1≤l≤⌊m−14⌋}$, $V1={vj(k−1)|j=4l+2,0≤l≤⌊m−24⌋}∪{vj(k−1)|j=4l−1,1≤l≤⌊m−14⌋}∪{vm(k−1),vmk}$ and V0 = V (G) (V1V2). Clearly, (V0, V1, V2) is a partition of V (G). Define f on V (G) by f(v) = i for any vVi, where 0 ≤ i ≤ 2. It is obvious that f is a strong Roman dominating function of G. Therefore, $γStR(G)≤f(V(G))=m(4k+1)+36$.

### Lemma 2.4.

([1]) Let G be a connected graph of order n. Then$γStR(G)≥⌈n+12⌉$.

By the following result, we improve the above result for a connected graph G with ∆(G) ≤ 4.

### Theorem 2.5

Let G be a connected graph of order n with ∆(G) ≤ 4. Then$γStR(G)≥⌈3n5⌉$.

Proof

Let f be a γStR-function of G, and let B0 = {wV (G)| f(w) = 0}, B1 = {wV (G)| f(w) = 1} and B2 = {wV (G)| f(w) ≥2}. Let $B2i={w∈B2||N(w)∩B0|=i}$ for i = 1, 2, 3, 4. Let $B01={w∈B0||N(w)∩B2|=1}$ and $B02={w∈B0||N(w)∩B2|≥2}$. Clearly (B0, B1, B2) is a partition of V (G), $(B21,B22,B23,B24)$ is a partition of B2 and $(B01,B02)$ is a partition of B0. Hence, $n=|B0|+|B1|+|B2|$, $|B2|=|B21|+|B22|+|B23|+|B24|$ and $|B0|=|B01|+|B02|$. Among all γStR-function of G, let f be chosen so that |B1| is maximized.

### Claim 1

$B21=∅$.

Proof

Suppose that $B21=∅$. Say $v∈B21$ and N(v) ∩ B0 = {u}. Define f′ on V (G) by f′(x) = f(x) for xV (G) − {u, v}, f′(u) = 1 and f′(v) = 1. Obviously f′ is a γStR-function of G with |B1| more than f, which is a contradiction.

### Claim 2

$B23=∅$.

Proof

Suppose that $B23=∅$. Say $v∈B23$ and N(v)∩B0 = {u1, u2, u3}. Define f′ on V (G) by f′(x) = f(x) for xV (G) − {u1, v}, f′(u1) = 1 and f′(v) = 2. Obviously f′ is a γStR-function of G with |B1| more than f, which is a contradiction.

### Claim 3

Let $u∈B22$. Then $N(u)∩B0⊆B01$.

Proof

Say N(u) ∩B0 = {w1, w2}. Suppose that $w1∉B01$. So $w1∉B02$. Define f′ on V (G) by f′(x) = f(x) for xV (G)−{u, w2}, f′(u) = 1 and f′(w2) = 1. Obviously f′ is a γStR-function of G with |B1| more than f, which is a contradiction.

By Claim 1, $|B2|=|B22|+|B24|$. Let E(B0, B2) denote the edge set between B0 and B2. It is obvious that $|B01|+2|B02|≤|E(B0,B2)|≤2|B22|+4|B24|$. So, $|B0|+|B02|≤2|B22|+4|B24|$. Hence, $n+|B02|≤|B1|+3|B22|+5|B24|$. Hence $γStR(G)=|B1|+2|B22|+3|B24|=23(n+12|B1|+2|B22|+72|B24|−|B0|)≥23(n+|B02|+12(|B1|−|B24|)).$and $γStR(G)=|B1|+2|B22|+3|B24|=|B1|+3(2|B22|3)+5(3|B24|5)≥34(|B1|+3|B22|+5|B24|)≥35(n+|B02|)≥35n.$Therefore, the result follows, since γStR(G) is an integer number.

### Strong Roman Domination Number of Pm□Pk

In this section, we investigate the strong Roman domination number of PmPk.

### Theorem 3.1

For any positive integer k, $γStR(P2□Pk)=⌈4k3⌉$.

Proof

By Observation 2.1, if k ≡ 0(mod 3), $γStR(P2□Pk)≤4k3=⌈4k3⌉$. By Observation 2.2, if k ≡ 1(mod 3), $γStR(P2□Pk)≤2(2k+1)3=⌈4k3⌉$. By Observation 2.3, if k ≡ 2(mod 3), $γStR(P2□Pk)≤4k+13=⌈4k3⌉$. Hence, in any case, $γStR(P2□Pk)≤⌈4k3⌉$. Among all γStR-function of P2Pk, let f be chosen so that |B1| is maximized.

It is obvious that $B24=∅$. By inequality (2.1) in Theorem 2.5, it follows that $γStR(P2□Pk)≥23(2k+|B02|+12|B1|)≥⌈43⌉.$Therefore, $γStR(P2□Pk)=⌈4k3⌉.$

### Theorem 3.2

For any positive integer k, γStR(P3Pk) = 2k.

Proof

By Observation 2.1, γStR(P3Pk) = γStR(PkP3) ≤ 2k.

Among all γStR-function of P3Pk, let f be chosen so that |B1| is maximized.

By Claim 2 in Theorem 2.5, $B23=∅$.

By inequality (2.1) in Theorem 2.5, it follows that $γStR(P3□Pk)≥23(3k+|B02|+12(|B1|−|B24|)).$In order to prove γStR(P3Pk) ≥2k, it is sufficient to prove that $2|B02|+|B1|≥|B24|$. If $B24=∅$, then it holds obviously. Hence, we may assume that $B24=∅$. It is obvious that $B24⊆ℛ2$. Now we define a function $g:B24→B02∪B1$ as follows:

For any u, $v∈B24$, d(u, v) ≥2. Suppose that u = v2i, v = v2j and , where ji ≥ 2. We discuss it from the following cases.

• Case 1: j = i + 2. That is u = v2i and v = v2(i+2). Then $v2(i+1)∈B02$. Define g(u) = v2(i+1).

• Case 2: j = i + 3. That is u = v2i and v = v2(i+3). If v1(i+1)B1, then define g(u) = v1(i+1). If f(v1(i+1)) ≥2, then $v2(i+1)∈B02$ and define g(u) = v2(i+1). If v1(i+1)B0, then f(v1(i+2)) = 3 and $v1(i+2)∈B23$, which is a contradiction.

• Case 3: j ≥ i+4. If v1(i+1)B1, then define g(u) = v1(i+1). If f(v1(i+1)) ≥2, then $v2(i+1)∈B02$ and define g(u) = v2(i+1). We may assume that f(v1(i+1)) = 0. Then 2 ≤ f(v1(i+2)) ≤ 3. Since $B23=∅$, f(v1(i+2)) = 2. Without loss of generality, we may assume that f(v3(i+1)) = 0 and f(v3(i+2)) = 2. If f(v2(i+2)) = 1, then define g(u) = v2(i+2). If f(v2(i+2)) = 0, then $v2(i+2)∈B02$ and define g(u) = v2(i+2). If f(v2(i+2)) ≥2, then $v2(i+1)∈B02$ and define g(u) = v2(i+1).

Let $h=max{j|v2j∈B24}$. If hk − 2, then by a similar way as Case 3, there exists a vertex vij such that $vij∈B02∪B1$, where i ∈ {1, 2, 3} and j ∈ {h+1, h+2}. So we define g(v2h) = vij. If h = k − 1, then f(v1k) = 1 and v1kB1. So we define g(v2h) = v1k.

Hence, for any $u∈B24$, there exists $w∈B02∪B1$ such that g(u) = w. Furthermore, for any u, $v∈B24$, if uv, then g(u) ≠ g(v). Hence, $|B02|+|B1|≥|B24|$. So $γStR(P3□Pk)≥23(3k+|B02|+12(|B1|−|B24|))≥2k.$

Therefore, γStR(P3Pk) = 2k.

### Lemma 3.3

For any positive integer k, $γStR(P4□Pk)≤⌈8k3⌉$.

Proof

Let G = P4Pk. By Observation 2.1, if k ≡ 0(mod 3), $γStR(P4□Pk)≤8k3=⌈8k3⌉$. By Observation 2.2, if k ≡ 1(mod 3), $γStR(P4□Pn)≤4(2k+1)3=⌈8k3⌉+1$. By Observation 2.3, if k ≡ 2(mod 3), $γStR(P4□Pn)≤4(4k+1)6=⌈8k3⌉$.

Let G = P4P4. Let V3 = {v32}, V2 = {v11, v14, v44}, V1 = {v23, v41} and V0 = V (G)(V1V2V3). Clearly, (V0, V1, V2, V3) is a partition of V (G). Define f4 on V (G) by f4(v) = i for any vVi, where 0 ≤ i ≤ 3. It is obvious that f4 is a strong Roman dominating function of G. Therefore, $γStR(G)≤|f4(V(G))|=11=⌈8k3⌉$, where k = 4.

Let G = P4P7. Let V3 = {v21, v35}, V2 = {v13, v14, v17, v42, v43, v47}, V1 = {v26} and V0 = V (G) (V1V2V3). Clearly, (V0, V1, V2, V3) is a partition of V (G). Define f7 on V (G) by f7(v) = i for any vVi, where 0 ≤ i ≤ 3. It is obvious that f7 is a strong Roman dominating function of G. Therefore, $γStR(G)≤|f7(V(G))|=19=⌈8k3⌉$, where k = 7.

For k ≥ 10, let k = 7+3t. Let V3 = {v21, v35}, $V2={v13,v14,v17,v42,v43,v47}∪{v1(2+6j),v2(4+6j),v3(4+6j),v4(2+6j)|j=1,2,…,⌈t2⌉}∪{v1(7+6j),v2(5+6j),v3(5+6j),v4(7+6j)|j=1,2,…,⌈t+12⌉−1}$,V1 = {v26} and V0 = V (G)(V1V2V3). Clearly, (V0, V1, V2, V3) is a partition of V (G). Define fk on V (G) by fk(v) = i for any vVi, where 0 ≤ i ≤ 3. It is obvious that fk is a strong Roman dominating function of G. Therefore, $γStR(G)≤|fk(V(G))|=⌈8k3⌉$.

### Lemma 3.4

For any positive integer k ≥ 4, $γStR(P4□Pk)≥{⌈8k3⌉if k=4,5,6,7⌈13(8k−⌊k8⌋+1)⌉if k≥8.$

Proof

Among all γStR-function of P4Pk, let f be chosen so that |B1| is maximized. Then $B21=B23=∅$. By inequality (2.1) in Theorem 2.5, it follows that $γStR(P4□Pk)≥23(4k+|B02|+12(|B1|−|B24|)).$

If $B24=∅$, then $γStR(P4□Pk)≥⌈8k3⌉$. Hence, we may assume that $B24=∅$. It is obvious that $B24⊆ℜ2∪ℜ3$.

### Claim 1

Suppose for j ∈ {2, 3, · · · , k − 1}. Then .

Proof

Without loss of generality, we can assume that $v2j∈B24$. Then v2(j−1), v2(j+1), v3jB0. If $v3(j+1)∈B24$, then d(v3(j+1)) = 4 and jk − 2. Define a function f′ on V (G) by f′(x) = f(x) for xV (G) − {v3(j+1), v3(j+2), v4(j+1)}, f′(v3(j+1)) = 1, f′(v3(j+2)) = 1 and f′(v4(j+1)) = 1. Then f′ is γStR-function of P4Pk with |B1| more than |B1| in f, which is a contradiction. Hence $v3(j+1)∉B24$. Similarly, $v3(j−1)∉B24$. So, .

### Claim 2

Let $h=min{j|vij∈B24}$. Then .

Proof

Without loss of generality, we can assume that $v2h∈B24$. Then 2 ≤ hk−1. If h = 2, then v11B1. So .

Suppose that h ≥ 3 and . Hence, for any vertex , $vij∈B01$ or $vij∈B22$. By Claim 3 in Theorem 2.5, $v1(h−1),v1(h−2),v3(h−1),v4h∈B01$. In order to dominate v1(h−1), f(v1(h−2)) = 2. Hence, $v3(h−2)∈B01$. In order to dominate v3(h−1), f(v4(h−1)) = 2. Hence, f(v4(h−2)) = 2. If h = 3, then $v4(h−2)∈B21$, which is a contradiction. If h = 4, then f(v1(h−3)) = 2 and $v2(h−3),v3(h−3),v4(h−3)∈B01$. Then $v1(h−3)∈B21$, which is a contradiction. If h ≥ 5, then $v1(h−4),v2(h−4),v4(h−4)∈B01$. Hence, f(v3(h−4)) = 3 and $v3(h−4)∈B24$, which is a contradiction. Hence, .

### Claim 3

Let $l=max{j|vijB24}$. Then .

Proof

Without loss of generality, we can assume that $v2l∈B24$. Then lk − 1. If l = k− 1, then v1kB1. So .

Suppose that lk − 2 and . Hence, for any vertex , $vij∈B01$ or $vij∈B22$. Then $v1(l+1),v2(l+2),v3(l+1)∈B01$. In order to dominate v1(l+1), f(v1(l+2)) = 2. Hence, $v3(l+2)∈B01$. In order to dominate v3(l+1), f(v4(l+1)) = 2. If l = k − 2, then f(v4(l+2)) = 2 and $v4(l+2)∈B21$, which is a contradiction. If l = k − 3, then f(v1(l+3)) = 2 and $v2(l+3),v3(l+3)∈B01$. So, $v1(l+3)∈B21$, which is a contradiction. If lk − 4, then f(v1(l+3)) = 2 and $v2(l+3),v3(l+3),v1(l+4)∈B01$. In order to dominate v3(l+2), f(v4(l+2)) = 2. Hence, $v4(l+3),v4(l+4)∈B01$. Hence, f(v3(l+4)) = 3 and $v3(l+4)∈B24$, which is a contradiction.

### Claim 4

Suppose that , and . If rj ≥ 5 or 2 ≤ rj ≤ 3, then .

Proof

If rj ≥ 5, then by a similar proof as Claim 2. Since rj ≥ 5, r − 4 ≥ j + 1. Hence, .

Suppose that rj = 2. Without loss of generality, we can assume that $v2j∈B24$. If $v2(j+2)∈B24$, then $v2(j+1)∈B02$. So . Suppose that $v3(j+2)∈B24$. If f(v1(j+2)) ≥1, then . If f(v1(j+2)) = 0, then v1(j+1)B1. So, .

Suppose that rj = 3. Without loss of generality, we can assume that $v2j∈B24$. Assume that $v2(j+3)∈B24$. If f(v1(j+1)) ≥1 or f(v1(j+2)) ≥1, then . If f(v1(j+1)) = 0 and f(v1(j+2)) = 0, then v1(j+2) is not dominated by B2, which is a contradiction. Hence, .

Without loss of generality, we can assume that $v3(j+3)∈B24$. If f(v1(j+1)) = ≥1, f(v2(j+2)) = ≥1 or f(v1(j+3)) = ≥1, then . If f(v1(j+1)) = 0, f(v2(j+2)) = 0 and f(v1(j+3)) = 0, then f(v1(j+2)) = 3 and $v1(j+2)∈B23$

, which is a contradiction. Hence, .

### Remark

if r = j + 4, then may be hold. Assume that $v2j∈B24$. If , then f(v) is fixed for any v. That is, $v3(j+4)∈B24$, ${v1(j+2),v1(j+3),v4(j+1),v4(j+2)}⊆B22$ and .

### Claim 5

Suppose that , , and . If for lj+2 and , then .

Proof

Assume that $v2(j−4)∈B24$. By remark, $v3j∈B24$, $v1(j−1)∈B22$ and $v1j∈B01$. If lj ≥ 5 or 2 ≤ lj ≤ 3, then by Claim 4. Without loss of generality, we can assume that l = j + 4. Suppose that $v2(j+4)∈B24$. If v1(j+1)B1, then . Hence, $v1(j+1)∈B01$.

If f(v2(j+2)) ≥1 or f(v1(j+3)) ≥1, then . If f(v2(j+2)) = 0 and f(v1(j+3)) = 0, then $v1(j+2)∈B23$, which is a contradiction.

Without loss of generality, we can assume that $v3(j+4)∈B24$. If f(v4(j+1)) ≥1, f(v3(j+2)) ≥1 or f(v4(j+3)) ≥1, then . If f(v4(j+1)) = 0, f(v3(j+2)) = 0 and f(v4(j+3)) = 0, then f(v4(j+2)) = 3 and $v4(j+2)∈B23$, which is a contradiction.

Suppose that there exist two positive integer j and r such that , , , , , , and , where rj + 2. If and , then rj ≥ 4.

Suppose that there exist a positive integer j such that , , and . If and , then j ≥ 3.

By Claims 2–5, it follows that if k = 4, 5, 6 or 7, then $|B02|+|B1|−|B24|≥0$. So, $γStR(P4□Pk)≥8k3$. If k ≥ 8, then $|B02|+|B1|−|B24|≥−⌊k8⌋+1$. Hence, $γStR(P4□Pk)≥23(4k+|B02|+12(|B1|−|B24|))=8k3+13(2|B02|+|B1|−|B24|)≥13(8k−⌊k8⌋+1).$

Therefore, the result follows, since γStR(G) is an integer number.

By Lemma 3.3 and Lemma 3.4, we give the following.

### Corollary 3.5

For positive integer k ∈ {4, 5, 6, 7}, $γStR(P4□Pk)≤⌈8k3⌉$.

### Theorem 3.6

For any positive integer k ≥ 8, $⌈13(8k−⌊k8⌋+1)⌉≤γStR(P4□Pk)≤⌈8k3⌉$, and both bounds are sharp.

### Remark 3.7

In order to show the lower bound is sharp, define a function f on P4P17 by $f(ℛ1)={f(v11),f(v12),⋯,f(v1(17))}={2, 0, 0, 0, 2, 2, 0, 0, 2, 0, 0, 2, 2, 0, 0, 0, 2},f(ℛ2)={f(v21),f(v22),⋯,f(v2(17))}= {0, 0, 3, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 3, 0, 0},f(ℛ3)={f(v31),f(v32),⋯,f(v3(17))}= {0, 1, 0, 0, 0, 0, 3, 0, 1, 0, 3, 0, 0, 0, 0, 1, 0},f(ℛ4)={f(v41),f(v42),⋯,f(v4(17))}= {2, 0, 0, 2, 2, 0, 0, 0, 2, 0, 0, 0, 2, 2, 0, 0, 2}.$It is obvious that f is a strong Roman dominating function of P4P17 and γStR(P4P17) ≤ 45. Since $⌈13(8k−⌊k8⌋+1)⌉=45$ for k = 17, it follows that $γStR(P4□P17)=⌈13(8k−⌊k8⌋+1)⌉$.

In order to show the upper bound is sharp, define a function f on P4P9 by $f(ℛ1)={f(v11),f(v12),⋯,f(v19)}={2, 0, 0, 0, 2, 2, 0, 0, 2},f(ℛ2)={f(v21),f(v22),⋯,f(v29)}= {0, 0, 3, 0, 0, 0, 0, 1, 0},f(ℛ3)={f(v31),f(v32),⋯,f(v39)}= {0, 1, 0, 0, 0, 0, 3, 0, 0},f(ℛ4)={f(v41),f(v42),⋯,f(v49)}= {2, 0, 0, 2, 2, 0, 0, 0, 2}.$It is obvious that f is a strong Roman dominating function of P4P9 and $γStR(P4□P9)≤24=⌈8k3⌉$. Since $⌈13(8k−⌊k8⌋+1)⌉=24$ for k = 9, it follows that $γStR(P4□P9)=⌈8k3⌉$.

### Acknowledgements

This research was financially supported by Changwon National University in 2019.

1. MP. Álvarez-Ruiz, T. Mediavilla-Gradolph, SM. Sheikholeslami, JC. Valenzuela-Tripodoro, and IG. Yero. On the strong Roman domination number of graphs. Discrete Appl. Math.., 231(2017), 44-59.
2. EJ. Cockayne, PM. Dreyer. Dreyer, SM. Hedetniemi, and ST. Hedetniemi. Roman domination in graphs. Discrete Math.., 278(2004), 11-22.
3. CS. ReVelle, and KE. Rosing. Defendents imperium romanum: a classical problem in military strategy. Amer. Math. Monthly., 107(7)(2000), 585-594.
4. I. Stewart. Defend the roman empire!. Sci. Amer.., 281(6)(1999), 136-138.