Some Progress on the Double Roman Domination in Graphs

Abstract

For a graph G = (V,E), a double Roman dominating function (or just DRDF) is a function f : V → {0, 1, 2, 3} having the property that if f(v) = 0 for a vertex v, then v has at least two neighbors assigned 2 under f or one neighbor assigned 3 under f, and if f(v) = 1, then vertex v must have at least one neighbor ω with f(ω) ≥ 2. The weight of a DRDF f is the sum f(V ) = Σv∈Vf(v), and the minimum weight of a DRDF on G is the double Roman domination number of G, denoted by γdR(G). In this paper, we derive sharp upper and lower bounds on γdR(G) + γdR(Ḡ) and also γdR(G)γdR(Ḡ) ,where Ḡ is the complement of graph G. We also show that the decision problem for the double Roman domination number is NP- complete even when restricted to bipartite graphs and chordal graphs.

Keywords

• roman domination
• double roman domination
• 05c69