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) \rightarrow \{-1, 1\}\) is said to be a signed star dominating function of \(G\) if \(\sum_{e \in E_G(v)} f(e) \geq 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 \(frac{n}{2}\leq \gamma_{SS}(T) \leq 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\).