M.Sc Student M.Sc Thesis Segalescu Nurit Majority Operator on Finite and Infinite Graphs Department of Mathematics PROFESSOR EMERITUS Abraham Berman

Abstract

This work addresses different properties of the majority operator on graphs. Initially each vertex in the graph is colored black or white. The majority operator M colors each vertex in the graph according to the color of the majority of its neighbors, maintaining the color of the vertex if it has an equal number of black and white neighbors. The process of sequentially operating the majority operator M on a finite graph converges: it either reaches fixed coloring or becomes periodic with period two. The work conjectures that the maximal number of rounds to convergence is smaller or equal to the number of vertices in the graph. For graph G and coloring x, the set of white vertices W0  is called dynamic monopoly if after a finite number of rounds all the vertices are colored white. W0 is called static monopoly, 2-round monopoly or monotone dynamo if respectively the convergence occurs in one round, two rounds, or if during the process a white vertex never turns black. Results from the literature show that for a graph with n vertices every static monopoly is of order W(Ön); every 2-round dynamo is of order W(Ön), every monotone monopoly is of order W(Ön). The current work shows that for a tree with n vertices there cannot exist a static monopoly with n/3 (or less) vertices, and that each 2-round dynamo is bigger then n/3. Additionally, it is proven that if for a tree there exists a monopoly of k vertices then the number of vertices in the tree is no larger than 11k-2.