Computational Complexity of Domination Integrity in Graphs

Abstract

In a graph G, those dominating sets S which give minimum value for |S| + m G−S , where m G−S denotes the maximum order of a component of G−S, are called dominating integrity sets of G briefly called DI-sets of G . This concept combines two important aspects namely domination and integrity in graphs. In this paper, we show that the decision problem domination integrity is NP-complete even when restricted to planar or chordal graphs.