Bounds on the signed domination number of a graph

Let G = (V, E) be a simple graph on vertex set V and define a function f: V → {−1, 1}. The function f is a signed dominating function if for every vertex x ∈ V, the closed neighborhood of x contains more vertices with function value 1 than with −1. The signed domination number of G, γs(G), is the minimum weight of a signed dominating function on G. We give a sharp lower bound on the signed domination number of G γs (G) is the minimum weight of a signed dominating function on G. We give a sharp lower bound on the signed domination number of a general graph with a given minimum and maximum degree, generalizing a number of previously known results. Using similar techniques we give upper and lower bounds for the signed domination number of some simple graph products: the grid Pj × Pk, Cj × Pk and Cj × Ck. For fixed width, these bounds differ by only a constant.