Upper minus domination in regular graphs (Q1567668): Difference between revisions

A minus dominating function of a graph \(G\) is a function \(f: V(G)\to \{-1,0,1\}\) such that the sum of its values over the closed neighbourhood \(N[v]\) of any vertex \(v\) of \(G\) is at least \(1\). (The closed neighbourhood \(N[v]\) is the set consisting of \(v\) and of all vertices adjacent to \(v\) in \(G\).) A minus dominating function \(f\) of \(G\) is minimal, if for any minus dominating function \(g\) of \(G\) the inequalities \(g(x)\leq f(x)\) for all \(x\in V(G)\) imply \(g= f\). The symbol \(f(V(G))\) denotes \(\sum_{x\in V(G)} f(x)\). The maximum value of \(f(V(G))\) taken over all minimal minus dominating functions \(f\) of \(G\) is the upper minus domination number \(\Gamma^-(G)\) of \(G\). The main result states that if \(G\) has \(n\) vertices and is regular of degree \(r\), then \(\Gamma^-(G)\leq (r+ 1)n/(r+ 3)\) for even \(r\) and \(\Gamma^-(G)\leq (r^2+ 1)n/(r+ 1)\) for odd \(r\). At the end, \(\Gamma^-(G)\) is related to the upper signed domination number \(\Gamma_s(G)\), which is a similar numerical invariant of a graph.