کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419626 | 683842 | 2013 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Rainbow domination in the lexicographic product of graphs Rainbow domination in the lexicographic product of graphs](/preview/png/419626.png)
A kk-rainbow dominating function of a graph GG is a map ff from V(G)V(G) to the set of all subsets of {1,2,…,k}{1,2,…,k} such that {1,…,k}=⋃u∈N(v)f(u){1,…,k}=⋃u∈N(v)f(u) whenever vv is a vertex with f(v)=0̸f(v)=0̸. The kk-rainbow domination number of GG is the invariant γrk(G)γrk(G), which is the minimum sum (over all the vertices of GG) of the cardinalities of the subsets assigned by a kk-rainbow dominating function. We focus on the 22-rainbow domination number of the lexicographic product of graphs and prove sharp lower and upper bounds for this number. In fact, we prove the exact value of γr2(G∘H) in terms of domination invariants of GG except for the case when γr2(H)=3γr2(H)=3 and there exists a minimum 22-rainbow dominating function of HH such that there is a vertex in HH with the label {1,2}{1,2}.
Journal: Discrete Applied Mathematics - Volume 161, Issues 13–14, September 2013, Pages 2133–2141