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∈N_G(v)} f(u) ≤ 1$ for all $v ∈ V$ where $N_G(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.