Upper Signed \(k\)-Domination Number in Graphs

Abstract

A signed \(k\)-dominating function of a graph \(G = (V, E)\) is a function \(f: V \rightarrow \{+1,-1\}\) such that \(\sum_{u \in N_G[v]} f(u) \geq k\) for each vertex \(v \in V\). A signed \(k\)-dominating function \(f\) of a graph \(G\) is minimal if no \(g \leq f\) is also a signed \(k\)-dominating function. The weight of a signed \(k\)-dominating function is \(w(f) = \sum_{v \in V} f(v)\). The upper signed \(k\)-domination number \(\Gamma_{s,k}(G)\) of \(G\) is the maximum weight of a minimal signed \(k\)-dominating function on \(G\). In this paper, we establish a sharp upper bound on \(\Gamma _{s,k}(G)\) for a general graph in terms of its minimum and maximum degree and order, and construct a class of extremal graphs which achieve the upper bound. As immediate consequences of our result, we present sharp upper bounds on \(\Gamma _{s,k}(G)\) for regular graphs and nearly regular graphs.