Difference between 2 2 -rainbow domination and Roman domination in graphs
A 2 2 -rainbow dominating function f f of a graph G G is a function f:V(G)?2{1,2} f : V ( G ) ? 2 { 1 , 2 } such that, for each vertex v?V(G) v ? V ( G ) with f(v)=0? f ( v ) = 0? , ?u?NG(v)f(u)={1,2} ? u ? N G ( v ) f ( u ) = { 1 , 2 } . The minimum of ?v?V(G)|f(v)| ? v ? V ( G ) | f ( v ) | over all such functions is called the 2 2 -rainbow domination number ?r2(G) ? r 2 ( G ) . A Roman dominating function g g of a graph G G , is a function g:V(G)?{0,1,2} g : V ( G ) ? { 0 , 1 , 2 } such that, for each vertex v?V(G) v ? V ( G ) with g(v)=0 g ( v ) = 0 , v v is adjacent to a vertex u u with g(u)=2 g ( u ) = 2 . The minimum of ?v?V(G)g(v) ? v ? V ( G ) g ( v ) over all such functions is called the Roman domination number ?R(G) ? R ( G ) . Regarding 0? 0? as 0 0 , these two dominating functions have a common property that the same three integers are used and a vertex having 0 0 must be adjacent to a vertex having 2 2 . Motivated by this similarity, we study the relationship between ?R(G) ? R ( G ) and ?r2(G) ? r 2 ( G ) . We also give some sharp upper bounds on these dominating functions. Moreover, one of our results tells us the following general property in connected graphs: any connected graph G G of order n?3 n ? 3 contains a bipartite subgraph H=(A,B) H = ( A , B ) such that ?(H)?1 ? ( H ) ? 1 and |A|?|B|?n/5 | A | ? | B | ? n / 5 . The bound on |A|?|B| | A | ? | B | is best possible.
roman domination number bipartite subgraph rainbow domination number