Strict majority functions on graphs
Michael A. Henning, H.R. Hind · Journal of Graph Theory · 1998
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. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 49–56, 1998