×

Some NP-complete results on signed mixed domination problem. (English) Zbl 1389.05130

Summary: Let \(G = \left({V, E} \right)\) be a simple graph with vertex set \(V\) and edge set \(E\). A signed mixed dominating function of \(G\) is a function \(f:V \cup E \to \left\{ { - 1, 1} \right\}\) such that \(\sum {_{y \in {N_m}\left(x \right) \cup \left\{ x \right\}}f\left(y \right) \geq 1} \) for every element \(x \in V \cup E\), where \({N_m}\left(x \right)\) is the set of elements of \(V \cup E\) adjacent or incident to \(x\). The weight of \(f\) is \(w\left(f \right) = \sum {_{x \in V \cup E}f\left(x \right)} \). The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of the signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI