{k}-domination for chordal graphs and related graph classes

In this work we obtain a new graph class where the { k } -dominating function problem ( { k } -DOM) is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. Firstly, by relating this problem with the k-dominating function problem (k-DOM), we prove that { k } -DOM is polynomial time solvable for strongly chordal graphs. Besides, by expressing the property involved in k-DOM in Counting Monadic Second-order Logic, we obtain that both problems are linear time solvable for bounded tree-width graphs. Finally, we show that { k } -DOM is linear time solvable for spider graphs.