[<i>k</i>]-Roman Domination in Digraphs

Abstract

Let D=(V(D),A(D)) be a finite, simple digraph and k a positive integer. A function f:V(D)→{0,1,2,…,k+1} is called a [k]-Roman dominating function (for short, [k]-RDF) if f(AN−[v])≥|AN−(v)|+k for any vertex v∈V(D), where AN−(v)={u∈N−(v):f(u)≥1} and AN−[v]=AN−(v)∪{v}. The weight of a [k]-RDF f is ω(f)=∑v∈V(D)f(v). The minimum weight of any [k]-RDF on D is the [k]-Roman domination number, denoted by γ[kR](D). For k=2 and k=3, we call them the double Roman domination number and the triple Roman domination number, respectively. In this paper, we presented some general bounds and the Nordhaus–Gaddum bound on the [k]-Roman domination number and we also determined the bounds on the [k]-Roman domination number related to other domination parameters, such as domination number and signed domination number. Additionally, we give the exact values of γ[kR](Pn) and γ[kR](Cn) for the directed path Pn and directed cycle Cn.

Keywords

• [<i>k</i>]-Roman dominating function
• [<i>k</i>]-Roman domination number
• domination number
• signed domination number
• Nordhaus–Gaddum bound