The Signed Domination Numbers in Graphs

Abstract

For any integer $k\ge 1$, a signed (total) $k$-dominating function is a function $f:V(G)\to \{-1,1\}$ satisfying $\sum _{u\in N(v)}f(u)>k$ ($\sum _{w\in N[v]}f(w)\ge 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}^{\prime }(G)$, resp.). In this paper, several sharp lower bounds of these numbers for general graphs are presented.