Signed domination in regular graphs and set-systems

Suppose G is a graph on n vertices with minimum degree r. Using standard ra ndom methods it is shown that there exists a two-coloring of the vertices o f 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 num ber 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 Hada mard matrix of order r, a bipartite r-regular graph is constructed on 4r ve rtices with signed domination number at least (1/2) root r- 0(1). The deter mination of lim(n-->)gamma(s)(G)/n remains open and is conjectured to be Th eta(1/root r). (C) 1999 Academic Press.