The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs

The k-domination problem is to find a minimum cardinality vertex set D of a graph such that every vertex of the graph is within distance k from some vertex of D, where k is a positive integer. The k-stability problem is to find a maximum cardinality vertex set S such that the distance between any two distinct vertices of S is greater than k. For sun-free chordal graphs, $2k$-stability and k-domination are dual problems. In particular, a minimum cardinality set of vertices D such that every vertex is within distance k of D has the same cardinality as a maximum cardinality set of vertices S such that the distance between every pair of vertices in S is greater than $2k$. To obtain this result we establish some theorems about the powers and radius of chordal graphs. Efficient algorithms for both problems on sun-free chordal graphs are obtained by transforming them to solvable cases of the clique covering and vertex packing problems. We also prove the NP-completeness of both problems on bipartite and chordal graphs.