Opinion functions on trees

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 [3n/2] - 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 [2/3(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 [2/3[p/2]] + 2 ≤ maj(T) ≤ [p/2] + 2. We establish the majority index for the class of trees called comets.