Minus domination in regular graphs (Q1910590): Difference between revisions

A minus dominating function of a graph \(G\) with vertex set \(V\) is a function \(f: V\to \{- 1, 0, 1\}\) with the property that the sum of its values over a closed neighbourhood of each vertex of \(G\) is at least 1. (The closed neighbourhood of a vertex \(v\) in \(G\) is a set consisting of \(v\) and all vertices which are adjacent to \(v\) in \(G\).) The minimum of \(\sum_{v\in V} f(v)\) taken over all minus dominating functions of \(G\) is called the minus domination number of \(G\) and denoted by \(\gamma^-(G)\). The reviewer has proved that for every regular graph \(G\) of degree 3 the inequality \(\gamma^-(G)\geq n/4\) holds, where \(n\) is the number of vertices of \(G\). The authors of the present paper generalize this result by proving that \(\gamma^-(G)\geq n/(r+ 1)\) for each regular graph \(G\) of degree \(r\), where \(r\) is an arbitrary integer, and this bound is sharp.