𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


On Harmonic Functions on Trees
✍ Alicia CantΓ³n; JosΓ© L. FernΓ‘ndez; Domingo Pestana; JosΓ© M. RodrÍguez πŸ“‚ Article πŸ“… 2001 πŸ› Springer Netherlands 🌐 English βš– 255 KB
Consensus functions defined on trees
✍ F.R. McMorris; Dean Neumann πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 497 KB
Dictatorial consensus functions on n-tre
✍ Jean-Pierre BarthΓ©lemy; F.R. McMorris; R.C. Powers πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 417 KB
On path entropy functions for rooted tre
✍ A. Meir; J.W. Moon πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 323 KB

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

Zeta Functions of Discrete Groups Acting
✍ Bryan Clair; Shahriar Mokhtari-Sharghi πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 198 KB

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