Opinion functions on trees Original Research Article

A two-valued function f defined on the vertices of a graph G = (V,E), f : V → {−1, 1}, is an opinion function. The positive value of f, denoted by pos f, is the number of vertices that are assigned the value +1 under f. For each vertex v of G, the vote(v) is the sum of the function values of f over the closed neighborhood of v. If vote(v) ⩾ 1, then we say that the vote of v is aye. A unanimous function of G is an opinion function for which every vertex votes aye. The unanimity index of G is unan(G) = min{pos f | f is a unanimous function of G} . We show that the maximum number of ayes that can occur in a tree with an opinion function of positive value n ⩾ 2 is ⌊3n2⌋ − 1. We then determine which trees have unanimous functions with positive value n (⩾ 2) attaining this value. We show that the range of values for the unanimity index of trees of order p > 1 is ⌊23(p+2)⌋ to p, and we characterize those trees with unanimity index reaching the lower bound. A majority function of a graph G is an opinion function for which more than half the vertices vote aye. The majority index of G, denoted by maj(G), is maj(G) = min{pos f | f is a majority function of G}. For any tree of order p ⩾ 2, we show that ⌊23⌊p2⌋⌋ + 2 ⩽ maj(T) ⩽ ⌊p2⌋ + 2. We establish the majority index for the class of trees called comets.