Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set   of a graph G=(V,E)G=(V,E) is a subset TDkTDk of V such that every vertex in V is adjacent to at least k   vertices of TDkTDk. In minimum k-tuple total dominating set problem (Mink-Tuple Total Dom Set), it is required to find a k-tuple total dominating set of minimum cardinality and Decide Mink-Tuple Total Dom Set is the decision version of Mink-Tuple Total Dom Set problem. In this paper, we show that Decide Mink-Tuple Total Dom Set is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that Mink-Tuple Total Dom Set can be solved in polynomial time. We also propose some hardness results and approximation algorithms for Mink-Tuple Total Dom Set problem.

► We study on algorithmic aspects of the problem of finding minimum k  -tuple total dominating set. ► We prove that for any k>0k>0, the problem of finding minimum k-tuple total dominating set is NP-hard for split graphs and bipartite graphs. ► We show that a minimum k-tuple total dominating set can be found for chordal bipartite graphs in polynomial time. ► We present some hardness and approximation results on the problem of finding minimum k-tuple total dominating set.