Opinion functions on trees
β Scribed by Lowell W. Beineke; Michael A. Henning
- Book ID
- 104113754
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 638 KB
- Volume
- 167-168
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
β¦ Synopsis
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 I 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 L~J -1. We then determine which trees have unanimous functions with positive value n (>i 2) attaining this value. We show that the range of values for the unanimity index of trees of order p > 1 is L2(p+2)J 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{posfl f is a majority function of G}. For any tree of order p >t 2, we show that ~2 L2ej j + 2 ~< maj(T) ~< L2eJ + 2. We establish the majority index for the class of trees called comets.
π SIMILAR VOLUMES
Ifu is a terminal node of a rooted tree T. with n terminal nodes, let h(u) = ~f (d(v)) where the sum is over all interior nodes v in the path from the root of T. to u, d(v) is the out-degree of v, and 1" is a non-negative cost function. The path entropy function h(T.) = ~h(u), where the sum is over
This paper generalizes Bass' work on zeta functions for uniform tree lattices. Using the theory of von Neumann algebras, machinery is developed to define the zeta function of a discrete group of automorphisms of a bounded degree tree. The main theorems relate the zeta function to determinants of ope