Premium
Strict majority functions on graphs
Author(s) -
Henning Michael A.,
Hind Hugh R.
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199805)28:1<49::aid-jgt6>3.0.co;2-f
Subject(s) - combinatorics , mathematics , conjecture , vertex (graph theory) , graph , discrete mathematics , function (biology) , evolutionary biology , biology
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