Global Majority Consensus by Local Majority Polling on Graphs of a Given Degree Sequence

Mohammed Amin Abdullah, Moez Draief

Suppose in a graph $G$ vertices can be either red or blue. Let $k$ be odd. At each time step, each vertex $v$ in $G$ polls $k$ random neighbours and takes the majority colour. If i…