A tight upper bound for 2-rainbow domination in generalized Petersen graphs ?
Let f f be a function that assigns to each vertex a subset of colors chosen from a set C={1,2,,k} C = { 1 , 2 ,  , k } of k k colors. If ?u?N(v)f(u)=C ? u ? N ( v ) f ( u ) = C for each vertex v?V v ? V with f(v)=0? f ( v ) = 0? , then f f is called a k k -rainbow dominating function  (k k RDF) of G G where N(v)={u?V?uv?E} N ( v ) = { u ? V ? u v ? E } . The weight  of f f , denoted by w(f) w ( f ) , is defined as w(f)=?v?V|f(v)| w ( f ) = ? v ? V | f ( v ) | . Given a graph G G , the minimum weight among all weights of k k RDFs, denoted by ? rk ( G ) , is called the k k -rainbow domination number  of G G . Bres?ar and S?umenjak (2007) [5] gave an upper bound and a lower bound for ? r2 ( GP ( n , k ) ) . They showed that ? 4 n 5 ? ? ? r2 ( GP ( n , k ) ) ? n . In this paper, we propose a tight upper bound for ? r2 ( GP ( n , k ) ) when n?4k+1 n ? 4 k + 1 .
upper bound domination generalized petersen graphs rainbow domination