On Dynamic Monopolies of Cubic Graphs

On Dynamic Monopolies of Cubic Graphs

Abstract

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 recoloring process starts on a graph whose vertices are initially colored black and white and at each round, each vertex recolors itself with the color of the majority 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 target set). In this paper, we study the reversible and the irreversible majority based recoloring processes over 3-regular (cubic) graphs and derive upper and lower bounds for the minimum size of a dynamic monopoly for both of these processes.

References