Outer independent double Roman domination

摘要

An outer independent double Roman dominating function (OIDRDF) of a graph G is a function h from V(G) to {0, 1, 2, 3} for which each vertex with label 0 is adjacent to a vertex with label 3 or at least two vertices with label 2, and each vertex with label 1, is adjacent to a vertex with label greater than 1; and all vertices labeled by 0 is independent. The weight of an OIDRDF h is ∑w ∈ V(G)h(w), and the outer independent double Roman domination number γoidR(G) is the minimum weight of an OIDRDF on G. In this article, we provide various bounds on γoidR(G) and we show that its determining is NP-complete on chordal and bipartite graphs. Moreover, we establish Nordhaus–Gaddum bounds for γoidR(G)+γoidR(G¯).