# The Perfect Roman Domination Number of the Cartesian Product of Some Graphs

Authors: Ahlam Almulhim; Abolape Deborah Akwu; Bana Al Subaiei
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A perfect Roman dominating function on a graphG is a function f:VG⟶0,1,2 for which every vertex v with fv=0 is adjacent to exactly one neighbor u with fu=2. The weight of f is the sum of the weights of the vertices. The perfect Roman domination number of a graph G, denoted by γRpG, is the minimum weight of a perfect Roman dominating function on G. In this paper, we prove that if G is the Cartesian product of a path Pr and a path Ps, a path Pr and a cycle Cs, or a cycle Cr and a cycle Cs, where r,s>5, then γRpG≤2/3G.


---

## Body

## 1. Introduction and Preliminaries

All graphs considered in this work are simple, finite, and undirected. LetG=V,E be a graph. We denote the cardinality of V by G. Two vertices u,v∈V are adjacent when uv∈E. The open neighborhood of a vertex v∈V is the set Nv=u|uv∈E while the closed neighborhood of a vertex v∈V is the set Nv=Nv∪v. The number of vertices of a path is its length. We denote a path of length n by Pn. We denote the cycle graph with n vertices by Cn.A dominating set of a graphG is a subset D of V where each vertex in VG\D is adjacent to at least one vertex in D. The domination number is the minimum cardinality of a dominating set of G, and it is usually denoted by γG. There is a large literature that covered the domination number. For basic definitions and concepts relating to this subject, we refer the reader to[1].A perfect dominating set of a graphG is a subset S of V where each vertex v∈VG satisfies Nv∩S=1. The perfect domination number is the minimum cardinality of a perfect domination set of G, and it is usually denoted by γpG. The study of perfect domination has received much attention in the literature, see for example [2, 3].A Roman dominating function on a graphG, denoted by RD-function, is a function f:VG⟶0,1,2 such that every vertex v with fv=0 is adjacent to at least one vertex u with fu=2. For any vertex v, the weight of v is its value under the function f while the weight of f, denoted by wf, is the sum ∑v∈VGfv. The Roman domination number of a graph G, denoted by γRG, is the minimum weight of a RD-function, i.e.,(1)γRG=minwffis a RD−function onG.Roman domination has been studied well and there are many research papers on this subject, such as [4, 5]. There are some variations on domination number and Roman domination number have been appeared in the literature such as total, week, and perfect [6–10]. In this paper, we continue the investigation of perfect Roman domination.A perfect Roman dominating function on a graphG is a function f:VG⟶0,1,2 for which every vertex v with fv=0 is adjacent to exactly one neighbor u with fu=2. We denote a perfect Roman dominating function by PRD-function. The weight of f, denoted by wf, is the sum ∑v∈VGfv. The perfect Roman domination number of a graph G, denoted by γRpG, is the minimum weight of a PRD-function, i.e.,(2)γRpG=minwffis a PRD−function onG.The investigation of perfect Roman domination was initiated by Henning et al. in [7] on trees and then Henning and Klostermeyer considered this subject on regular graphs [11]. More recent work on perfect Roman domination can be found in [12–15].Roman domination in product graphs has become an attractive topic in the study of domination and much work has been done in this area such as Cartesian product [16], lexicographic product [6, 17], rooted product [8, 18], and direct product [18]. Perfect Roman domination in product graphs has been considered for corona product in [13]. In this work, we studied perfect Roman domination in the Cartesian product of paths and paths, paths and cycles, and cycles and cycles.LetH1 and H2 be two graphs. The Cartesian product graph of H1 and H2, denoted by H1□H2, is the graph with VH1×VH2 as its set of vertices, and two vertices u,v,u′,v′∈H1□H2 are adjacent if either(1)
u=u′ and vv′∈EH2 or(2)
v=v′ and uu′∈EH1The graphPr□Ps is a grid graph with r columns and s rows, see Figure 1.Figure 1
Grid graphP5□P4.We denote the vertex in rowi and column j by ai,j. The graph Pr□Cs is a cylinder grid graph which is a grid graph, with r columns and s rows, and some extra edges between the vertices of the first and the last rows, see Figure 2. The graph Cr□Cs is a torus grid graph which is a cylinder grid graph with some extra edges between the vertices of the first and last columns, see Figure 3. So VPr□Ps=VPr□Cs=VCr□Cs and EPr□Ps⊆EPr□Cs⊆ECr□Cs.Figure 2
Cylinder grid graphP5□C4.Figure 3
Torus grid graphC5□C4.


## 2. Discussion

In this section, we present an upper bound for the perfect Roman domination number of a grid graph, a cylinder grid graph, and a torus grid graph.Theorem 1.
Letr,s>5. If G∈ {Pr□Ps, Pr□Cs, Cr□Cs}, γRpG≤2/3G.Proof.
The statement will be a result from the following three cases.Case 1.
r=3k or s=3k for some integer k. If r=3k, label each vertex in column number 2+3m,m∈0,1,…,k−1 with 2, and label the remainder vertices with 0. See Figure 4. It is not hard to see that this labeling produces a perfect Roman domination function of weight equals to 2/3G where G∈Pr□Ps,Pr□Cs,Cr□Cs. In a similar way, if s=3k, label each vertex in row number 2+3m,m∈0,1,…,k−1 with 2, and label the remainder vertices with 0.
We need the following function for the remaining cases. Define a functionf:VG⟶0,1,2 as follows:(3)fai,j=2,ifi≡0mod3andj≡3mod6,2,ifi≡1mod3andj≡1mod6,2,ifi≡2mod3andj≡5mod6,1,ifi≡0mod3andj≡0mod6,1,ifi≡1mod3andj≡4mod6,1,ifi≡2mod3andj≡2mod6,0,otherwise.
The functionf has a pattern recurring every six columns, and it also has a pattern recurring every three rows, as shown in Figure 5. It is not hard to see that every vertex ai,j with fai,j=0 has exactly one neighbor labelled 2, except some vertices in the first and last rows and possibly in the first and last columns. So we need to modify f slightly depending on the values of r and s.Figure 4
r=3k.Figure 5
The functionf.Case 2.
r=3k+1. If s is a multiple of three, we are in a situation symmetric to Case 1, and we are done. So we may assume that s is not a multiple of three. We divide this case to two subcases.Case 2.1.s=3l+1 for some integer l. If r≡1mod6, define a function f′:VG⟶0,1,2 such that(4)f′ai,j=1,ifi=1andj≡3mod6,1,ifi=sandj≡5mod6,fai,j,otherwise.Then,f′ is a PRD-function on G where G∈ {Pr□Ps, Pr□Cs, Cr□Cs}, see Figure 6. Note that if j≡1mod6, ∑i=1sf′ai,j=2s−1/3+2. If j≡2mod6, ∑i=1sf′ai,j=s−1/3. If j≡3mod6, ∑i=1sf′ai,j=2s−1/3+1. If j≡4mod6, ∑i=1sf′ai,j=s−1/3+1. If j≡5mod6, ∑i=1sf′ai,j=2s−1/3+1. If j≡0mod6, ∑i=1sf′ai,j=s−1/3. Therefore,(5)wf′=93s−1+5k2+23s−1+2=3s−1+5r−16+23s−1+2=12sr+16s+13r+1<12sr+16sr=23sr=23G.Inequality (5) follows from the fact that r,s≥7.Ifr≡4mod6, define a function f′:VG⟶0,1,2 such that(6)f′ai,j=2,ifi=1andj=r,1,ifi=sandj≡5mod6,1,ifi=1,j≡3mod6andj≠r−1,1,ifi≡2mod3,i≠2andj=r,fai,j,otherwise.Then,f′ is a PRD-function on G where G∈ {Pr□Ps, Pr□Cs, Cr□Cs}, see Figure 7. If j≡1mod6, ∑i=1sf′ai,j=2s−1/3+2. If j≡2mod6, ∑i=1sf′ai,j=s−1/3. If j≡3mod6, ∑i=1sf′ai,j=2s−1/3+1. If j≡4mod6 and j≠r, ∑i=1sf′ai,j=s−1/3+1. If j=r, ∑i=1sf′ai,j=2s−1/3+1. If j≡5mod6, ∑i=1sf′ai,j=2s−1/3+1. If j≡0mod6, ∑i=1sf′ai,j=s−1/3. Thus,(7)wf′=3s−1+5r−46+73s−1+4=12sr+13s+13r+13<12sr+16sr=23sr=23G.Inequality (7) follows from the fact that r,s≥7.Case 2.2.s=3l+2 for some integer l. Assume that r≡1mod6. Define a function f′:VG⟶0,1,2 such that(8)f′ai,j=1,ifi=1andj≡3mod6,1,ifi=1andj≡5mod6,1,ifi=sandj≡1mod6,1,ifi=sandj≡3mod6,fai,j,otherwise.Then,f′ is a PRD-function on G where G∈ {Pr□Ps,Pr□Cs, Cr□Cs}, see Figure 8.Ifj≡1mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡2mod6, ∑i=1sf′ai,j=s−2/3+1. If j≡3mod6, ∑i=1sf′ai,j=2s−2/3+2. If j≡4mod6, ∑i=1sf′ai,j=s−2/3+1. If j≡5mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡0mod6, ∑i=1sf′ai,j=s−2/3. Therefore,(9)wf′=3s−2+10r−16+23s−2+3=12sr+16s+23r+1,<12sr+16sr=23sr.Inequality (9) follows from the fact that r≥7 and s≥8. Assume that r≡4mod6. Define a function f′:VG⟶0,1,2 such that(10)f′ai,j=2,ifi=1andj=r,2,ifi=sandj=r,1,ifi=1andj≡5mod6,1,ifi=sandj≡1mod6,1,ifi=1,j≡3mod6andj≠r−1,1,ifi=s,j≡3mod6andj≠r−1,1,ifi≡2mod3,i∉2,sandj=r,fai,j,otherwise.Then,f′ is a PRD-function on G where G∈ {Pr□Ps, Pr□Cs, Cr□Cs}, see Figure 9. If j≡1mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡2mod6, ∑i=1sf′ai,j=s−2/3+1. If j≡3mod6 and j≠r−1, ∑i=1sf′ai,j=2s−2/3+2. If j=r−1, ∑i=1sf′ai,j=2s−2/3. If j≡4mod6 and j≠r, ∑i=1sf′ai,j=s−2/3+1. If j=r, ∑i=1sf′ai,j=2s−2/3+3. If j≡5mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡0mod6, ∑i=1sf′ai,j=s−2/3. Therefore,(11)wf′=3s−2+10r−46+2s−2+7=12sr+23r+13,<12sr+16sr=23sr.Inequality (11) follows from the fact that r,s>5.Figure 6
The functionf′ where r=3k+1,s=3l+1 and r≡1mod6.Figure 7
The functionf′ where r=3k+1,s=3l+1 and r≡4mod6.Figure 8
The functionf′ where r=3k+1,s=3l+2 and r≡1mod6,Figure 9
The functionf′ where r=3k+1,s=3l+2 and r≡4mod6.Remark 1.
In both cases, i.e.,r≡1mod6 and r≡4mod6, the function f′ is also a PRD-function on the Cartesian product graphCr□Ps.Case 3.
r=3k+2. If s=3l+1 then we are in a situation symmetric to Case 2 (see Remark 1). So we may assume that s=3l+2.
Assume thatr≡2mod6. Define a function f′:VG⟶0,1,2 such that(12)f′ai,j=1,ifi=1andj≡3mod6,1,ifi=1andj≡5mod6,1,ifi=sandj≡1mod6,1,ifi=sandj≡3mod6,2,ifi≡1mod3andj=r,0,ifi≡2mod3andj=r,fai,j,otherwise.
Then,f′ is a PRD-function on G whereG∈ {Pr□Ps,Pr□Cs,Cr□Cs}, see Figure 10. If j≡1mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡2mod6 and j≠r then ∑i=1sf′ai,j=s−2/3+1, and if j=r then ∑i=1sf′ai,j=2s−2/3+2. If j≡3mod6, ∑i=1sf′ai,j=2s−2/3+2. If j≡4mod6, ∑i=1sf′ai,j=s−2/3+1. If j≡5mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡0mod6, ∑i=1sf′ai,j=s−2/3. Therefore,(13)wf′=3s−2+10r−26+43s−2+5=12sr+13s+23r+1,<12sr+16sr=23sr.
Inequality (13) follows from the fact that r,s≥8. Assume that r≡5mod6. Define a function f′:VG⟶0,1,2 such that(14)f′ai,j=1,ifi=1andj≡3mod6,1,ifi=1,j≡5mod6andj≠r,0,ifi≡1mod3andj=r−1,1,ifi≡2mod3andj=r−1,1,ifi=sandj≡3mod6,2,ifi≡1mod3andj=r,0,ifi≡2mod3,i≠sandj=r,1,ifi=sandj=r,fai,j,otherwise.
Then,f′ is a PRD-function on G whereG∈ {Pr□Ps, Pr□Cs, Cr□Cs}, see Figure 11. If j≡1mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡2mod6, ∑i=1sf′ai,j=s−2/3+1. If j≡3mod6, ∑i=1sf′ai,j=2s−2/3+2. If j≡4mod6, ∑i=1sf′ai,j=s−2/3+1. If j≡5mod6, ∑i=1sf′ai,j=2s−2/3+3. If j≡0mod6, ∑i=1sf′ai,j=s−2/3. Therefore,(15)wf′=3s−2+10r−56+83s−2+10=12sr+16s+23r+43<12sr+16sr=23sr.
Inequality (15) follows from the fact that r,s>5.Figure 10
The functionf′ where r=3k+2,s=3l+2 and r≡2mod6.Figure 11
The functionf′ where r=3k+2,s=3l+2 and r≡5mod6.


## 3. Conclusions

In this paper, we discussed the perfect Roman domination number of the Cartesian product of a path and a path, a path and a cycle, and cycle and a cycle. We found that in these three graphs the perfect Roman domination number is not greater than 2/3 of the cardinality of its vertices. Concerning the further plans for our work, we will investigate the perfect Roman domination number of the Cartesian product of trees.



---

*Source: 1957027-2022-10-18.xml*