Roman Reinforcement Numbers of Digraphs

Abstract

Let $D=(V,A)$ be a finite and simple digraph. A Roman dominating function (RDF) on $D$ is a labeling $f:V(D)\to \{0,1,2\}$ such that every vertex $v$ with label $0$ has a vertex $w$ with label $2$ such that $wv$ is an arc in $D$. The weight of an RDF $f$ is the value $\omega (f)=\sum _{v\in V}f(v)$. The Roman domination number of a digraph $D$, denoted by ${\gamma }_R(D)$, equals the minimum weight of an RDF on $D$. The Roman reinforcement number $r_R(D)$ of a digraph $D$ is the minimum number of arcs that must be added to $D$ in order to decrease the Roman domination number. In this paper, we initiate the study of Roman reinforcement number in digraphs and we present some sharp bounds for $r_R(D)$. In particular, we determine the Roman reinforcement number of some classes of digraphs.