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 log r/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) r−O(1). The determination of limn→∞ γs(G)/n remains open and is conjectured to be Θ(1/r).