On Dynamic Monopolies of Cubic Graphs

Majority based recoloring processes over graphs are used to model the spread of fault in distributed computing and communication networks.We consider two of the most common variations: the reversible process and the irreversible process. The reversible majority based recoloringprocess starts on a graph whose vertices are initially colored black and white and at each round, each vertex recolors itself with the color of themajority of its neighbors. The irreversible process is similar to the reversible process except that it forbids white vertices from becoming black.If the process eventually reaches an all-white global state, the set of initially white vertices is called a dynamic monopoly (or a perfect targetset). In this paper, we study the reversible and the irreversible majority based recoloring processes ov