The Signed Domination Numbers in Graphs

Abstract

For any integer \(k \geq 1\), a signed (total) \(k\)-dominating function is a function \(f : V(G) \rightarrow \{-1, 1\}\) satisfying \(\sum_{u \in N(v)} f(u) > k\) (\(\sum_{w \in N[v]} f(w) \geq k\)) for every \(v \in V(G)\), where \(N(v) = \{u \in V(G) | uv \in E(G)\}\) and \(N[v] = N(v) \cup \{v\}\). The minimum of the values of \(\sum_{v \in V(G)} f(v)\) , taken over all signed (total) \(k\)-dominating functions \(f\), is called the signed (total) \(k\)-domination number and is denoted by \(\gamma_{kS}(G)\) (\(\gamma’_{kS}(G)\), resp.). In this paper, several sharp lower bounds of these numbers for general graphs are presented.