A Note on Roman Domination of Digraphs

Abstract

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of a digraph D, denoted by γ(D), is the minimum cardinality of a dominating set of D. A Roman dominating function (RDF) on a digraph D is a function f : V (D) → {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 ω (f) =Σv∈V(D)f(v). The Roman domination number of a digraph D, denoted by γR(D), is the minimum weight of an RDF on D. In this paper, for any integer k with 2 ≤ k ≤ γ(D), we characterize the digraphs D of order n ≥ 4 with δ−(D) ≥ 1 for which γR(D) = (D) + k holds. We also characterize the digraphs D of order n ≥ k with γR(D) = k for any positive integer k. In addition, we present a Nordhaus-Gaddum bound on the Roman domination number of digraphs.

Keywords

• roman domination number
• domination number
• digraph
• nordhaus-gaddum
• 05c69
• 05c20