Algorithmic Aspects of Outer-Independent Double Roman Domination in Graphs

Let Formula: see text be graph. For any function Formula: see text, let Formula: see text, Formula: see text. The function Formula: see text is called an outer-independent double Roman dominating function (OIDRDF) if the following conditions are satisfied. (i) If Formula: see text, then Formula: see text or Formula: see text (ii) If Formula: see text, then Formula: see text (iii) Formula: see text is independent. The outer-independent double Roman domination number of Formula: see text is defined by Formula: see text is an OIDRDF OF Formula: see text. We prove that the decision problem MOIDRDP, corresponding to Formula: see text is NP-complete for split graphs. We also show that it is linear time solvable for connected threshold graphs and bounded treewidth graphs. Finally, we show that the MOIDRDP and domination are not equivalent in computational complexity aspects.