On the complexity of {k}-domination and k-tuple domination in graphs

G. ARGIROFFO; V. LEONI; P. TORRES

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2015 vol. 116 p. 556 - 561

0020-0190

 We consider two types of graph domination ---${k}$-domination and $k$-tuple domination, for a fixed positive integer $k$--- and provide new NP-complete as well as polynomial time solvable instances for their related decision problems.Regarding NP-completeness results, we solve the complexity of the ${k}$-domination  problem on split graphs, chordal bipartite graphs and planar graphs, left open in 2008. On the other hand, by exploiting Courcelle´s results on Monadic Second Order Logic, we obtain that both problems are polynomial time solvable for graphs with clique-width bounded by a constant. In addition, we give an alternative proof for the linearity of these problems on strongly chordal graphs.