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

فرض کنید (v,e) یک گراف ساده با مجموعه رئوس v بوده و f:v-{0,1,2}، یک تابع باشد که وزن آن به صورت ω (f)= σv∈v(g)f(v) تعریف می شود. گوییم راس v نسبت به تابع f محافظت شده است هرگاه 0 < (v) یا 0 = (f(v و r با راسی g مانند با 0 < (f(u مجاور باشد. تابع {0,1,2 + (vg : ، یک تابع احاطه گر هم رومی در نامیده میشود هرگاه (1) هر راس u با 0 = (fu حداقل با یک راس با 0 < (v) مجاور باشد و (2) هر راس با 0 < (f (v حداقل با یک راس با 0 = (f(u مجاور باشد، به f'(v) = f(v) — åblobs of': v(g) →-طوری که هر راس g نسبت به تابع 0,1,2}. (u) او (f(x) = f(x برای سایر رئوس , - x vg تعریف میشود، =1 1محافظت شده باشد. عدد احاطه ای هم رومی گراف g که با نماد (yer (g نمایش داده می شود، عبارت است از کمترین وزن در بین تمامی توابع احاطه گر هم -رومی گراف g .در این مقاله عدد احاطه ای هم -رومی شبکه ها را مطالعه کرده و مقدار دقیق این پارامتر را برای شبکه های p2 x pn و p3 x pn به دست می آوریم.

co-roman dominating of girds

abstractlet 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.introductionthroughout 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 definefs=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 functionf:v→0,1,2 satisfying the condition that every vertex u for which fu=0 is adjacent to atleast 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 resultstheorem 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.references1. 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.