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

ARGIROFFO, GABRIELA; LEONI, VALERIA; TORRES, PABLO

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; 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 fixedpositive integer $k$). Their related decision problems are both NPcompleteeven for bipartite graphs. In this work, we study somesubclasses of bipartite graphs. We prove the NP-completeness of bothproblems (for every fixed $k$) for bipartite planar graphs and we providean APX-hardness result for the total domination problem for bipartitesubcubic graphs.In addition, we introduce a more general variation of total domination(total $(r,m)$-domination) that allows us to design a specific lineartime algorithm for bipartite distance-hereditary graphs. In particular,it returns a minimum weight total ${k}$-dominating function forbipartite distance-hereditary graphs.