کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419713 | 683851 | 2009 | 4 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: 2-rainbow domination in generalized Petersen graphs P(n,3)P(n,3) 2-rainbow domination in generalized Petersen graphs P(n,3)P(n,3)](/preview/png/419713.png)
Assume we have a set of kk colors and we assign an arbitrary subset of these colors to each vertex of a graph GG. If we require that each vertex to which an empty set is assigned has in its neighborhood all kk colors, then this assignment is called a kk-rainbow dominating function of GG. The corresponding invariant γrk(G)γrk(G), which is the minimum sum of numbers of assigned colors over all vertices of GG, is called the kk-rainbow domination number of GG. B. Brešar and T.K. Šumenjak [On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007) 2394–2400] showed that ⌈4n5⌉≤γr2(P(n,k))≤n for any generalized Petersen graph P(n,k)P(n,k), where nn and kk are relatively prime numbers. And they proposed the question: Is γr2(P(n,3))=nγr2(P(n,3))=n for all n≥7n≥7 where nn is not divisible by 3? In this note, we show that γr2(P(n,3))≤n−1γr2(P(n,3))≤n−1 for all n≥13n≥13. Moreover, we show that γr2(P(n,3))≤n−⌊n8⌋+β, where β=0β=0 for n≡0,2,4,5,6,7,13,14,15n≡0,2,4,5,6,7,13,14,15 (mod 16) and β=1β=1 for n≡1,3,8,9,10,11,12n≡1,3,8,9,10,11,12 (mod 16).
Journal: Discrete Applied Mathematics - Volume 157, Issue 11, 6 June 2009, Pages 2570–2573