The algorithmic complexity of minus domination in graphs (Q1917346): Difference between revisions

A minus dominating function of a graph \(G\) with vertex set \(V\) is a function \(f : V \to \{- 1,0,1\}\) such that the sum of its values over any closed neighbourhood \(N [v]\) is at least one; the closed neighbourhood of a vertex \(v\) is the set \(N[v]\) consisting of \(v\) and of all vertices which are adjacent to \(v\). The weight of \(f\) is the sum of its values over \(V\). The minimum weight of a minus dominating function \(f\) of \(G\) is the minus domination number \(\gamma^- (G)\) of \(G\), the maximum weight of a minimal minus dominating function of \(G\) is the upper minus domination number \(\Gamma^- (G)\) of \(G\). The problem to determine whether \(\gamma^- (G) \leq j\) or \(\Gamma^- (G) \leq j\) for a given graph \(G\) and a given number \(j\) is proved to be NP-complete even when restricted to bipartite graphs or chordal graphs. A linear-time algorithm for finding a minimum minus dominating function in a tree is presented.