The Roman domination and domatic numbers of a digraph

Let $D$ be a simple digraph with vertex set $V$. A Roman dominating function (RDF) on a digraph $D$ is a function $f: V\rightarrow \{0,1,2\}$ satisfying the condition that every vertex $v$ with $f(v)=0$ has an in-neighbor $u$ with $f(u)=2$. The weight of an RDF $f$ is the value $\sum_{v\in V}f(v)$. The Roman domination number of a digraph $D$ is the minimum weight of an RDF on $D$. A set $\{f_1,f_2,\dots,f_d\}$ of Roman dominating functions on $D$ with the property that $\sum_{i=1}^df_i(v)\le2$ for each $v\in V$, is called a Roman dominating family (of functions) on $D$. The maximum number of functions in a Roman dominating family on $D$ is the Roman domatic number of $D$, denoted by $d_{R}(D)$. In this paper we continue the investigation of the Roman domination number, and we initiate the study of the Roman domatic number in digraphs. We present some bounds for $d_{R}(D)$. In addition, we determine the Roman domatic number of some digraphs.

Abstract licence: CC BY-SA

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.