LOWER AGAINST NUMBER IN GRAPHS
Weiliang Zhao · 2012
A negative function of a graph G = (V,E) is a function f : V → {−1,+1} such that for every vertex v, the sum of the values of f over the closed neighborhood of v is at most 1. A negative function f is maximal if there does not exist a negative function g, f 6 g, for which g(v) ≥ f(v) for every v ∈ V. The weight of a negative function is w(f) = P v∈V (G) f(v). The lower against number � ∗ (G) of G is the minimum weight of a maximal negative function on G. In this paper we establish a sharp lower bound on � ∗ (G) for general graphs. Our result generalizes previous results for regular graphs and nearly regular graphs with minimum degree being even.