Some more remarks on domination in cubic graphs (Q5939926)

Let \(G\) be a graph and \(f\) a mapping of its vertex set \(V(G)\) into \(\{-1,1\}\). For each vertex \(v\in V(G)\) let \(N[v]\) be the set consisting of \(v\) and of all vertices adjacent to \(v\) in \(G\). Let NEWLINE\[NEWLINEf(N[v])= \sum_{x\in N[v]} f(x)\quad\text{and}\quad f(V(G))= \sum_{x\in V(G)}f(x).NEWLINE\]NEWLINE If \(f(N[v])\geq 1\) for each \(v\in V(G)\), then \(f\) is called a signed dominating function on \(G\). If instead of the set \(\{-1,1\}\) we take the set \(\{-1,0,1\}\), then such a function \(f\) is a minus dominating function on \(G\). The minimum of \(f(V(G))\) taken over all signed (respectively minus) dominating functions \(f\) on \(G\) is called the signed (respectively minus) domination number of \(G\). The signed domination number of \(G\) is denoted by \(\gamma_s(G)\), its minus domination number by \(\gamma^-(G)\). A signed dominating function \(f\) is minimal, if for no other signed dominating function \(g\) the inequality \(f(x)\geq g(x)\) holds for all \(x\in V(G)\). The maximum of \(f(V(G))\) taken over all minimal signed dominating functions \(f\) on \(G\) is called the upper signed domination number \(\Gamma_\delta(G)\) of \(G\). Analogously the upper minus domination number \(\Gamma^-(G)\) is defined.NEWLINENEWLINENEWLINEA nearly \(k\)-regular graph is a graph all of whose vertices have degree \(k\) or \(k-1\). For a nearly \((k+1)\)-regular graph \(G\) with \(n\) vertices the inequalities \(\Gamma_s(G)\leq n(k+ 2)(k^2+ 6k+ 4)\) for \(k\) even and \(\Gamma_s(G)\leq n(k^2+ 3k+ 4)/(k^2+ 5k+ 2)\) for \(k\) odd are proved; these bounds are sharp. The inequality \(\gamma^-(G)\leq{5\over 8}n\) for every connected cubic graph different from the Petersen graph and the inequality \(\Gamma^-(G)\leq \lfloor{3\over 4} n-1\rfloor\) for every cubic graph are proved, where \(n\) is the number of vertices.