On the mixed domination problem in graphs

A mixed dominating set of a simple graph G=(V,E) is a subset D⊆V∪E such that every vertex or edge not in D is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to determine a minimum mixed dominating set of G. This paper studies mixed domination in graphs from an algorithmic point of view. In particular, a linear-time labeling algorithm for the mixed domination problem in cacti is presented. In addition, we fix an incomplete proof of the NP-completeness of the mixed domination problem in split graphs Zhao et al. (2011) [23]. Finally, we establish a primal–dual algorithm for the mixed domination problem in trees.