Sharp Lower Bounds on Signed Domination Numbers of Digraphs

Abstract

Let $D$ be a finite and simple digraph with vertex set $V(D)$, and let $f:V(D)\to \{-1,1\}$ be a two-valued function. If $\sum _{x\in N_D^{-}[v]}f(x)\ge 1$ for each $v\in V(D)$, where $N_D^{-}[v]$ consists of $v$ and all vertices of $D$ from which arcs go into $v$, then $f$ is a signed dominating function on $D$. The sum $\sum _{v\in V(D)}f(v)$ is called the weight of $f$. The signed domination number, denoted by ${\gamma }_S(D)$, of $D$ is the minimum weight of a signed dominating function on $D$. In this work, we present different lower bounds on ${\gamma }_S(D)$ for general digraphs, show that these bounds are sharp, and give an improvement of a known lower bound obtained by Karami in 2009 [H. Karami, S.M. Sheikholeslami, A. Khodkar, Lower bounds on the signed domination numbers of directed graphs, Discrete Math. 309 (2009), 2567-2570]. Some of our results are extensions of well-known properties of the signed domination number of graphs.