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.