On the Signed Star Domination Numbers of Trees

Abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A function $f:E(G)\to \{-1,1\}$ is said to be a signed star dominating function of $G$ if $\sum _{e\in E_G(v)}f(e)\ge 1$ for every $v\in V(G)$, where $E_G(v)=\{uv\in E(G)|u\in V(G)\}$. The minimum of the values of $\sum _{e\in E(G)}f(e)$, taken over all signed dominating functions $f$ on $G$, is called the signed star domination number of $G$ and is denoted by ${\gamma }_{SS}(G)$. In this paper, we prove that $fracn2\le {\gamma }_{SS}(T)\le n-1$ for every tree $T$ of order $n$, and characterize all trees on $n$ vertices with signed star domination number $\frac{n}{2}$, $\frac{n+1}{2}$, $n-1$, or $n-3$.