M.Sc Thesis | |

M.Sc Student | Segalescu Nurit |
---|---|

Subject | Majority Operator on Finite and Infinite Graphs |

Department | Department of Mathematics |

Supervisor | PROFESSOR EMERITUS Abraham Berman |

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 *W _{0}*