Discrepancy and signed domination in graphs and hypergraphs

For a graph GG, a signed domination function of GG is a two-colouring of the vertices of GG with colours +1 and −1 such that the closed neighbourhood of every vertex contains more +1’s than −1’s. This concept is closely related to combinatorial discrepancy theory as shown by Füredi and Mubayi [Z. Füredi, D. Mubayi, Signed domination in regular graphs and set-systems, J. Combin. Theory Ser. B 76 (1999) 223–239]. The signed domination number of GG is the minimum of the sum of colours for all vertices, taken over all signed domination functions of GG. In this paper, we present new upper and lower bounds for the signed domination number. These new bounds improve a number of known results.