Some sharp bounds on the negative decision number of graphs

Let G = (V, E) be a graph. A function f : V → {-1, 1} is called a bad function of G if ∑uεNG(v) f (u) ≤ 1 for all v ε V , where NG(v) denotes the set of neighbors of v in G. The negative decision number of G, introduced in [12], is the maximum value of ∑vεV f (v) taken over all bad functions of G. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality for the negative decision number.