The Limited Packing and Multiple Domination problems in graphs

M. P. DOBSON ; V. LEONI; G. NASINI

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Año: 2011 vol. 111 p. 1108 - 1113

0020-0190

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 $P_4$-tidy graphs. From this result, we derive that they are polynomial time solvable in $P_4$-lite graphs, giving in this way an answer to a question stated by Liao and Chang on the domination side.