On the algorithmic complexity of kk-tuple total domination

For a fixed positive integer kk, a kk-tuple total dominating set   of a graph GG is a set D⊆V(G)D⊆V(G) such that every vertex of GG is adjacent to at least kk vertices in DD. The kk-tuple total domination problem   is to determine a minimum kk-tuple total dominating set of GG. This paper studies kk-tuple total domination from an algorithmic point of view. In particular, we present a linear-time algorithm for the kk-tuple total domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph, which include trees, block graphs, cacti and block-cactus graphs. We also establish NP-hardness of the kk-tuple total domination problem in undirected path graphs.