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.