Co-Roman dominating of girds

Khoeilr, Rana; soroudi, marzieh; Atapour, Maryam

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

Mendeley

Zotero

RefWorks

Khoeilr R, soroudi M, Atapour M. Co-Roman dominating of girds. mmr 2022; 8 (3) :80-90
URL: http://mmr.khu.ac.ir/article-1-2962-en.html

Co-Roman dominating of girds

Rana Khoeilr ^*

¹, Marzieh Soroudi²

, Maryam Atapour³

1- Azararbaijan Shahid Madani University , khoeilar@azaruniv.ac.ir
2- Azararbaijan Shahid Madani University
3- university of Bonab

Abstract: (783 Views)

Abstract
Let G = (V, E) be a simple graph with vertex set V and let f:V→0,1,2 be a function of weight ωf=v∈VGfv. 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':VG→0,1,2, defined by f'v=fv-1, f'u=1 and f'x=f(x) for x∈VG-{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 S⊆V(G) of vertices of a graph G and a function f:V(G)→R, we define
fS=v∈Sf(S). The weight of f is ωf=fV(G)=v∈VGfv.
A Roman dominating function on a graph G, abbreviated RD-function, is a function
f:V→0,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:V→0,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':VG→0,1,2, defined by f'v=fv-1, f'u=1 and f'x=f(x) for x∈VG-{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, ‎ γcrT≤2 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, Ǌ, (2001) 2nd ed.

Keywords: Roman dominating function, co-Roman dominating function, grid, Roman domination number, co-Roman domination number.

Full-Text [PDF 1763 kb] (335 Downloads)

Send email to the article author

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

Designed & Developed by : Yektaweb

Mathematical Researches

Related Websites

Site Keywords

Vote