The Signed Total Domination Number of Graphs

Abstract

Let \(G\) be a graph on \(2n\) vertices with minimum degree \(r\). We show that there exists a two-coloring of the vertices of \(G\) with colors \(-1\) and \(+1\), such that all open neighborhoods contain more \(+1\)’s than \(-1\)’s, and altogether the number of \(+1\)’s does not exceed the number of \(-1\)’s by more than \(O(\frac{n}{\sqrt{n}})\).