Bounds for Independent Roman Domination in Graphs

Abstract

A Roman dominating function on a graph $G$ is a function $f:V(G)\to \{0,1,2\}$ such that every vertex $u$ with $f(u)=0$ is adjacent to a vertex $v$ with $f(v)=2$. The weight of a Roman dominating function $f$ is the value $f(V(G))=\sum _{u\in V(G)}f(u)$. A Roman dominating function $f$ is an independent Roman dominating function if the set of vertices for which $f$ assigns positive values is independent. The independent Roman domination number $i_R(G)$ of $G$ is the minimum weight of an independent Roman dominating function of $G$.

We show that if $T$ is a tree of order $n$, then $i_R(T)\le \frac{4n}{5}$, and characterize the class of trees for which equality holds. We present bounds for $i_R(G)$ in terms of the order, maximum and minimum degree, diameter, and girth of $G$. We also present Nordhaus-Gaddum inequalities for independent Roman domination numbers.