Bounds on the Signed Roman k-Domination Number of a Digraph

Abstract

Let k be a positive integer. A signed Roman k-dominating function (SRkDF) on a digraph D is a function f : V (D) → {−1, 1, 2} satisfying the conditions that (i) Σx∈N−[v]f(x) ≥ k for each v ∈ V (D), where N−[v] is the closed in-neighborhood of v, and (ii) each vertex u for which f(u) = −1 has an in-neighbor v for which f(v) = 2. The weight of an SRkDF f is Σv∈V (D)f(v). The signed Roman k-domination number γksR(D) of a digraph D is the minimum weight of an SRkDF on D. We determine the exact values of the signed Roman k-domination number of some special classes of digraphs and establish some bounds on the signed Roman k-domination number of general digraphs. In particular, for an oriented tree T of order n, we show that γ2sR(T) ≥ (n + 3)/2, and we characterize the oriented trees achieving this lower bound.

Keywords

• signed roman k-dominating function
• signed roman k-domination number
• digraph
• oriented tree
• 05c69
• 05c20