On the Complexity of {k}-domination for Chordal Graphs

Abstract

In this work we obtain a new graph class where {k}-DOM is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. By relating this problem with 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. In this way we enlarge the family of graphs for which k-DOM is polynomial time solvable.