Volume 8, Issue 3 (Vol. 8,No. 3, 2022)                   mmr 2022, 8(3): 80-90 | Back to browse issues page

XML Persian Abstract Print


1- Azararbaijan Shahid Madani University , khoeilar@azaruniv.ac.ir
2- Azararbaijan Shahid Madani University
3- university of Bonab
Abstract:   (444 Views)
Abstract
Let G = (V, E) be a simple graph with vertex set V and let f:V0,1,2  be a function of weight ωf=vVGfv. A vertex v is protected with respect to f, if fv>0 or fv=0 and v is adjacent to a vertex u such that fu>0. The function f is a co-Roman dominating function, abbreviated CRDF if: (i) every vertex u with fu=0 is adjacent to a vertex v for which fv>0, and (ii) every vertex v with fv>0 has a neighbor u for which fu=0, such that each vertex of G is protected with respect to the function f':VG0,1,2, defined by  f'v=fv-1, f'u=1 and f'x=f(x) for xVG-{u,v}. The co-Roman domination number of a graph G, denoted by γcr(G), is the minimum weight of a co-Roman dominating function on G.
In this paper, we study the co-Roman domination number of grid graphs and we obtain this parameter for P2×Pn and P3×Pn.
Introduction
Throughout this paper, G is a simple connected graph with vertex set V=V(G) and edge set E=E(G) of order n and size m. The Cartesian product, G×H, of graphs G and H is a graph such that the vertex set of  G×H is the Cartesian product V(G) ×V(H); and two vertices (u,u') and (v,v') are adjacent in G×H if and only if either u=v and u' is adjacent to v' in H, or u'=v' and u is adjacent to v in G. The Cartesian product Pn×Pm is called a grid graph.
A set S of vertices in a graph G is called a dominating set if every vertex in V is either an element of S or is adjacent to an element of S. The domination number of G, denoted by γ(G), is the minimum cardinality of a dominating set of G. A γ(G)-set is a dominating set of G of size γ(G).
For a subset SV(G) of vertices of a graph G and a function f:V(G)→R, we define
fS=vSf(S). The weight of f is ωf=fV(G)=vVGfv.
A Roman dominating function on a graph G, abbreviated RD-function, is a function
f:V0,1,2 satisfying the condition that every vertex u for which fu=0 is adjacent to at
least one vertex v for which fv=2. The minimum weight of an RD-function on G is called the Roman domination number of G and is denoted by γRG. An RD-function with minimum weight γRG in G is called a γRG-function of G. The Roman domination was introduced by Cockayne et al. in [5].
Let f:V0,1,2  be a function. A vertex v is protected with respect to f, if fv>0 or fv=0 and v is adjacent to a vertex u such that fu>0. The function f is a co-Roman dominating function, abbreviated CRDF if: (i) every vertex u with fu=0 is adjacent to a vertex v for which fv>0, and (ii) every vertex v with fv>0 has a neighbor u for which fu=0  such that each vertex of G is protected with respect to the function f':VG0,1,2, defined by  f'v=fv-1, f'u=1 and f'x=f(x) for xVG-{u,v}. The co-Roman domination number of a graph G, denoted by γcr(G), is the minimum weight of a co-Roman dominating function on G. The concept of co-Roman domination was introduced by Arumugam and et. al [2] and was studied by Shao and et. al [9].
In this paper, we study the co-Roman domination number of grid graphs and we obtain this parameter for P2×Pn and P3×Pn. For a more thorough treatment of domination parameters and for terminology not presented here see [6], [7] and [10]. The following results are useful in this paper.
Proposition 1. [2] For a cycle Cn, n≥4, and for a path Pn, γcrCn=γcrPn=2 n5.
Proposition 2. [2]. For a graph G, γcrγR≤2 γ.
Proposition 3. [2] For any tree T of order n, γcrT2 n3.
Main Results
Theorem 1.     For n≥2,
γcrP2× Pn=2 n3+1n≡0,1 (mod 3)2 n3otherwise.
Theorem 2.     For n≥2,
γcrP3× Pn=nn≡1 (mod 3)n+1otherwise.
References
1. Amjadi J., Chellali M., Sheikholeslami S. M., Soroudi M., "On two open problems concerning weak Roman domination in trees",Australas. J. Combin, 74 (2019) 61-73.
2 Arumugam S., Ebadi K., Manrique M., "Co-Roman dominaton in graphs", Indian Acad.Sci. (Math. Sci), 125 (2015) 1-10.‎‎‎‎
3. Chambers E. W., Kinnersley B., Prince N., West D. B., "Extremal problems for Roman domination", SIAM J. Discrete. Math, 23 (2009) 1575-1586.‎‎‎
4. Chellali M., Haynes T. W., Hedetniemi S. T., "Bounds on weak Roman and 2-rainbow domination numbers"‎‎, ‎‎Discrete. Appl. Math., 178 ‎‎‎‎‎(2014) ‎‎‎‎‎‎‎27-32.‎‎‎‎‎
5. Cockayne E. J., ‎‎Dreyer Jr. P. A., ‎‎Hedetniemi S. M., Hedetniemi‎ S. T., "‎‎Roman domination in graphs", Discrete Math., 278‎‎‎‎ (2004) ‎‎‎‎‎‎‎‎‎11-22.‎‎
6. Haynes T. W., Hedetniemi S. T., Slater P. J., "Fundamentals of Domination in Graphs", Marcel Dekker, Inc, New York, (1998).
7. Haynes T. W., Hedetniemi S. T., Slater P. J., "Dominatin in Graphs: Advanced Topics", Marcel Dekker, Inc, New York, (1988).
8. Henning M. A., "Defending the Roman Empire-A new strategy‎‎", Discrete Math.‎, 266‎‎‎‎ (2003) 239-251.
9. Shao Z., Sheikholeslami S. M., Soroudi M., Volkmann L., Liu X., "On the co-Roman domination in graphs", Discuss. Math. Graph Theory, 39 (2019) 455-472.
10. West D. B., "Introduction to graph theory". Prentice Hall Inc., Upper Saddle River, NJ, (2001) 2nd ed.
 
Full-Text [PDF 1763 kb]   (187 Downloads)    
Type of Study: S | Subject: alg
Received: 2019/06/8 | Revised: 2023/06/18 | Accepted: 2021/02/2 | Published: 2022/12/20 | ePublished: 2022/12/20

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.