Chiang Mai Journal of Science

Given Given a vertex u of a connected simple graph G(V, E), let N(u) = {v | v ∈ V and (u, v) ∈ E}. We say that u dominates all vertices in N(u). Two distinct vertices u and v of G are said to be independent if (u, v) ∉ E. For any positive integer k, a subset Q of V is said to be a k-dominating set of G if every vertex v ∉ Q is dominated by at least k vertices in Q . Furthermore, if any two distinct vertices u and v of a k-dominating set D are independent, then D is said to be an independent k-dominating set of G. Let W(u) denote the weight of each vertex u of G. Finding an independent k-dominating set D of G such that σ(D) = Σu∈DW(u) is minimized is the main problem studied in this paper, called the WMIkD problem. The problem is called the MIkD problem for short if W(v) = 1, for all v ∈ V. For all fixed k ≥ 1, we first show that the MIkD problem on chordal bipartite graphs is NP-Hard. Second, an O(n)-time algorithm for the WMIkD problem on trees is designed, where n is the number of the vertices of the input graph. The third result extends the algorithm on trees to 4-cactus graphs and the time-complexity is still O(n). Keywords: independent k-dominating sets, chordal bipartite graphs, trees, p-cactus graphs, NP-Hard.