Extremal digraphs for an upper bound on the Roman domination number

Let D = (V, A) be a digraph. A Roman dominating function of a digraph D is a function f : V -> {0, 1, 2} such that every vertex u for which f (u) = 0 has an in-neighbor v for which f (v) = 2. The weight of a Roman dominating function is the value f (V) = Sigma(u is an element of V) f (u). The minimum weight of a Roman dominating function of a digraph D is called the Roman domination number of D, denoted by gamma(R)(D). In this paper, we characterize some special classes of oriented graphs, namely out-regular oriented graphs and tournaments satisfying gamma(R)(D) = n - Delta(+) (D) + 1. Moreover, we characterize digraphs D for which the equality gamma(R)(D)+gamma(R)((D) over bar) = n+3 holds, where (D) over bar is the complement of D. Finally, we prove that the problem of deciding whether an oriented graph D satisfies gamma(R)(D) = n - Delta(+) (D) + 1 is CO-NP-complete.