Minus domination in small-degree graphs (Q5928868)

Let \(G\) be a graph with vertex set \(V(G)\). A mapping \(f: V(G)\to \{-1,0,1\}\) is called a minus dominating function on \(G\), if \(f(N[v])= \sum_{x\in N[v]} f(x)\geq 1\) for each vertex \(v\in V(G)\), where \(N[v]\) denotes the closed neighbourhood of \(v\) in \(G\). The minimum of the values \(f(V(G))= \sum_{x\in V(G)}f(x)\), taken over all minus dominating functions \(f\) on \(G\), is called the minus domination number \(\gamma^-(G)\) of \(G\). The paper investigates the complexity of computing \(\gamma^-(G)\). It is proved that determinating \(\gamma^-(G)\) is NP-hard for planar graphs with minimum degree \(\Delta\leq 4\). But in graphs with \(\Delta\leq 4\) the number \(\gamma^-(G)\) can be approximated within some constant ratio in linear time. Some remrks are added which concern the (similarly defined) signed domination number.