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

G. R. ARGIROFFO; VALERIA LEONI; PABLO TORRES

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2015 vol. 115 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.