A 2-rainbow dominating function f of a graph G is a function f:V(G)→2~(1,2r) such that, for each vertex vV(G) with f(v)=Combining long solidus overlay, _(uNG)(v)f(u)=1,2r. The minimum of ～vV(G)f(v) over all such functions is called the 2-rainbow domination number γr2(G). A Roman dominating function g of a graph G, is a function g:V(G)→0,1,2r such that, for each vertex vV(G) with g(v)=0, v is adjacent to a vertex u with g(u)=2. The minimum of ～_(vV)(G)g(v) over all such functions is called the Roman domination number ~(γR)(G). Regarding Combining long solidus overlay as 0, these two dominating functions have a common property that the same three integers are used and a vertex having 0 must be adjacent to a vertex having 2. Motivated by this similarity, we study the relationship between ~(γR)(G) and ~(γr2)(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 of order n≥3 contains a bipartite subgraph H=(A,B) such that δ(H)≥1 and A-B≥n/5. The bound on A-B is best possible.
展开▼
