On the Complexity of the Labelled Domination Problem in Graphs

G. R. ARGIROFFO; VALERIA LEONI; PABLO TORRES

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH

Thomson Reuters

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

0969-6016

In 2008, Lee and Chang introduced a unified approach (labelled domination) to several domination problems ($k$-tuple domination, ${k}$-domination and $M$-domination, among others). The labelled domination problem is to find an $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 the class 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 labelled domination problem is polynomial-time solvable to the class of graphs having clique-width bounded by a constant.