Discrepancy and signed domination in graphs and hypergraphs

For a graph G , a signed domination function of G is a two-colouring of the vertices of G 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 G is the minimum of the sum of colours for all vertices, taken over all signed domination functions of G . In this paper, we present new upper and lower bounds for the signed domination number. These new bounds improve a number of known results.