THE NEGATIVE DECISION NUMBER IN GRAPHS
Changping Wang · 2008
A bad function is a function f: V (G) → {−1, 1} satisfying ∑ v∈N(v) f(v) ≤ 1 for every v ∈ V (G), where N(v) = {u ∈ V (G) | uv ∈ E(G)}. The f(v), taken over all bad functions f, is called the negative decision number and is denoted by βD(G). In this paper, several sharp upper bounds of this number for general graphs are presented. maximum of the values of ∑ v∈V (G)