Signed domination in regular graphs and set-systems

Suppose G is a graph on n vertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of G with colors, +1 and -1, such that all closed neighborhoods contain more 1's than - 1's, and all together the number of 1's does not exceed the number of -1's by more than (4 root logr/r + 1/r) n. For large r this greatly improves earlier results and is almost optimal, since starting with an Hadamard matrix of order r, a bipartite r-regular graph is constructed on 4r vertices with signed domination number at least (1/2) root r- 0(1). The determination of lim(n-->)gamma(s)(G)/n remains open and is conjectured to be Theta(1/root r). (C) 1999 Academic Press.