Minus domination in graphs (Q1297430): Difference between revisions

Let \(G\) be a graph with vertex set \(V\). A function \(f: V\to\{-1,0,1\}\) is called a minus dominating function on \(G\), if the sum of its values over the closed neighbourhood \(N[v]\) of an arbitrary vertex \(v\in V\) is at least 1. The weight \(w(f)\) is defined by \(\sum_{x\in V}f(x)\). The minimum of \(w(f)\) taken over all minus dominating functions \(f\) on \(G\) is called the minus domination number \(\gamma^-(G)\) of \(G\). If the set \(\{0,1\}\) is used instead of \(\{-1,0,1\}\), then we have the definition of the domination number \(\gamma(G)\) of \(G\). In the paper it is proved that \(\gamma(G)- \gamma^-(T)\leq (n-4)/5\) for every tree \(T\) with \(n\geq 4\) vertices. There exist outerplanar graphs, chordal graphs and bipartite graphs with \(\gamma^-(G)\) arbitrarily small. If the degrees of the vertices do not exceed 5, then \(\gamma^-(G)\) is nonnegative. At the end the minimum number \(p(n,\gamma^-)\) of vertices of a graph with \(n\) vertices and with the minus domination number \(\gamma^-\) is studied.