Strict Majority Functions on Graphs

An opinion function on a graph G = (V, E) is a function f: V → {-1, +1}. The vote of a vertex v is the sum of these function values over the closed neighborhood of v. A strict majority function on a graph G is an opinion function for which more than half of the vertices have a positive vote. The strict majority number of G is the minimum sum of the values in a strict majority function of G. We prove the conjecture of Cockayne and Mynhardt (Ars. Combin. 43 (1996), 235-245) that every tree has strict majority number at most 2. We also prove that every graph has strict majority number at most 4. Both bounds are sharp.