Bounding the rainbow domination number of a tree in terms of its annihilation number

A ۲-rainbow dominating function (۲RDF) of a graph G is a‎ ‎function f from the vertex set V(G) to the set of all subsets‎ ‎of the set \{۱,۲\} such that for any vertex v\in V(G) with‎ ‎f(v)=\emptyset the condition \bigcup_{u\in N(v)}f(u)=\{۱,۲\}‎ ‎is fulfilled‎, ‎where N(v) is the open neighborhood of v‎. ‎The ‎weight of a ۲RDF f is the value \omega(f)=\sum_{v\in V}|f‎ ‎(v)|‎. ‎The ۲-rainbow  domination number of a graph G‎, ‎denoted by \gamma_{r۲}(G)‎, ‎is the minimum weight of a ۲RDF of G‎. ‎The annihilation number a(G) is the largest integer k such‎ ‎that the sum of the first k terms of the non-decreasing degree‎ ‎sequence of G is at most the number of edges in G‎. ‎In this‎ ‎paper‎, ‎we prove that for any tree T with at least two vertices‎, ‎\gamma_{r۲}(T)\le a(T)+۱‎.

کلیدواژه ها:

annihilation number ، ۲-rainbow dominating function ، ۲-rainbow domination number