Transactions on Combinatorics (Sep 2013)
Bounding the rainbow domination number of a tree in terms of its annihilation number
Abstract
A {em 2-rainbow dominating function} (2RDF) of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all subsets of the set ${1,2}$ such that for any vertex $vin V(G)$ with $f(v)=emptyset$ the condition $bigcup_{uin N(v)}f(u)={1,2}$ is fulfilled, where $N(v)$ is the open neighborhood of $v$. The {em weight} of a 2RDF $f$ is the value $omega(f)=sum_{vin V}|f (v)|$. The {em $2$-rainbow domination number} of a graph $G$, denoted by $gamma_{r2}(G)$, is the minimum weight of a 2RDF of G. The {em 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_{r2}(T)le a(T)+1$.
