Perfect graphs of strong domination and independent strong domination Original Research Article

Let γ(G), i(G), γS(G) and iS(G) denote the domination number, the independent domination number, the strong domination number and the independent strong domination number of a graph G, respectively. A graph G is called γi-perfect (domination perfect) if γ(H)=i(H), for every induced subgraph H of G. The classes of γγS-perfect, γSiS-perfect, iiS-perfect and γiS-perfect graphs are defined analogously. In this paper we present a number of characterization results on the above classes of graphs. For example, characterizations of K4-free γSiS-perfect graphs and triangle-free γiS-perfect graphs are given. Moreover, the strong dominating set and independent strong dominating set problems as well as the weak dominating set and independent weak dominating set problems are shown to be NP-complete on a class of graphs. Several problems and conjectures are proposed.