Relating the annihilation number and the Roman domination

Abstract

A {\em Roman dominating function} (RDF) on a graph $G$ is a labeling$f\:$V (G)\rightarrow \{0, 1, 2\}$ such that every vertex withlabel 0 has a neighbor with label 2. The {\em weight} of an RDF$f$ is the value $\omega(f)=\sum_{v\in V}f (v)$. The {\em Romandomination number} of a graph $G$, denoted by $\gamma_R(G)$,equals the minimum weight of an RDF on 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 mostthe number of edges in $G$. In this paper, we prove that for anytree $T$ of order at least two, $\gamma_{R}(T)\le\frac{4a(T)+2}{3}$.