On the algorithmic complexity of k k -tuple total domination ?
For a fixed positive integer k k , a k k -tuple total dominating set  of a graph G G is a set D?V(G) D ? V ( G ) such that every vertex of G G is adjacent to at least k k vertices in D D . The k k -tuple total domination problem  is to determine a minimum k k -tuple total dominating set of G G . This paper studies k k -tuple total domination from an algorithmic point of view. In particular, we present a linear-time algorithm for the k k -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 k k -tuple total domination problem in undirected path graphs.
algorithm total domination block graph undirected path graph k k -tuple total domination k k k k k cactus np-complete