The multiple domination and limited packing problems in graphs

In this work we confront—from a computational viewpoint—the Multiple Domination problem, introduced by Harary and Haynes in 2000 among other variations of domination, with the Limited Packing problem, introduced in 2009. In particular, we prove that the Limited Packing problem is NP-complete for split graphs and for bipartite graphs, two graph classes for which the Multiple Domination problem is also NP-complete (Liao and Chang, 2003). For a fixed capacity, we prove that these two problems are polynomial time solvable in quasi-spiders. Furthermore, by analyzing the combinatorial numbers that are involved in their definitions applied to the join and the union of graphs, we show that both problems can be solved in polynomial time for P4-tidy graphs. From this result, we derive that they are polynomial time solvable in P4-lite graphs, giving in this way an answer to a question stated by Liao and Chang on the domination side.