Voting 'Against' in regular and nearly regular graphs
Changping Wang · Applicable Analysis and Discrete Mathematics · 2010
Let G = (V,E) be a graph. A function f : V (G)-> {-1,1} is called negative if ?vEN[v] f(v)?1 for every v E V(G): A negative function f of a graph G is maximal if there exists no negative function g such that g ? f and g(v) ? f(v) for every v E V: The minimum of the values of ?vEV f(v); taken over all maximal negative functions f, is called the lower against number and is denoted by ?*N (G): In this paper, we present lower bounds on this number for regular graphs and nearly regular graphs, and we characterize the graphs attaining those bounds.