Strict Majority Functions on Graphs

Michael A. Henning, Hugh R. Hind

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)49-56
Number of pages8
JournalJournal of Graph Theory
Issue number1
Publication statusPublished - May 1998
Externally publishedYes


  • Bounds
  • Strict majority function
  • Trees

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'Strict Majority Functions on Graphs'. Together they form a unique fingerprint.

Cite this