Complexity of k-tuple total and total {k}-dominations for some subclasses of bipartite graphs

ARGIROFFO, G.; LEONI, V.; TORRES, P.

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Año: 2018 vol. 138 p. 75 - 80

0020-0190

We consider two variations of graph total domination, namely, k-tuple total domination and total {k}-domination (for a fixed positive integer k). Their related decision problems are both NP-complete even for bipartite graphs. In this work, we study some subclasses of bipartite graphs. We prove the NP-completeness of both problems (for every fixed k) for bipartite planar graphs and we provide an APX-hardness result for the total domination problem for bipartite subcubic graphs. In addition, we introduce a more general variation of total domination (total (r,m)-domination) that allows us to design a specific linear time algorithm for bipartite distance-hereditary graphs. In particular, it returns a minimum weight total {k}-dominating function for bipartite distance-hereditary graphs.