Bounds on the nonnegative signed domination number of graphs

Abstract

The aim of this work is to investigate the nonnegative signed domination number ${\gamma }_s^{NN}$ with emphasis on regular, ($r+1$)-clique-free graphs and trees. We give lower and upper bounds on ${\gamma }_s^{NN}$ for regular graphs and prove that $n/3$ is the best possible upper bound on this parameter for a cubic graph of order $n$, specifically. As an application of the classic theorem of Turán we bound ${\gamma }_s^{NN}(G)$ from below, for an ($r+1$)-clique-free graph $G$ and characterize all such graphs for which the equality holds, which corrects and generalizes a result for bipartite graphs in [Electron. J. Graph Theory Appl. 4 (2) (2016), 231--237], simultaneously. Also, we bound ${\gamma }_s^{NN}(T)$ for a tree $T$ from above and below and characterize all trees attaining the bounds.