Roman domination in oriented trees

Abstract

Let D=(V,A) be a digraph of order n = |V|. 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)=∑u∈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 γR(D). In this paper, we characterize oriented trees T satisfying γR(T)+Δ+(T) = n+1.

Keywords

• roman domination, digraph, oriented tree