On the Complexity of Reverse Minus Domination on Graphs

Motivated by the concept of reverse signed domination, we introduce the reverse minus domination problem on graphs and study the problem from the algorithmic point of view. For strongly chordal graphs and distance-hereditary graphs, we show that the reverse minus domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees. For chordal graphs and bipartite planar graphs, however, we show that the decision problem corresponding to the reverse minus domination problem is NP-complete.