On the complexity of the Labelled Domination Problem in Graphs

ARGIROFFO, GABRIELA; LEONI, V.; TORRES, PABLO

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH

Wiley

Año: 2017 vol. 24 p. 355 - 367

0969-6016

In 2008, a unified approach (labeled domination) to several domination problems (k-tuple domination, {k}- domination, and M-domination, among others) was introduced. The labeled domination problem is to findan L-dominating function of minimum weight in a graph. It is an NP-complete problem even when restricted to split graphs and bipartite graphs. On the other hand, it is known to be polynomial-time solvable for theclass of strongly chordal graphs. In this paper, we state explicit formulas that relate the domination numbers considered. These relationships allow us to enlarge the family of graphs where the labeled domination problem is polynomial-time solvable to the class of graphs having cliquewidth bounded by a constant.