احاطه گری هم-رومی در شبکه ها

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, NJ, (2001) 2nd ed.