Computational Complexity of Domination Integrity in Graphs

Computational Complexity of Domination Integrity in Graphs

R.Sundareswaran, V.Swaminathan

[PDF]

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 (briey 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.

Keywords

Integrity, Domination Integrity