In a graph theoretical model of the spread of fault in distributed computing and communication networks, each element in the network is represented by a vertex of a graph where edges connect pairs of communicating elements, and each colored vertex corresponds to a faulty element at discrete time periods. Majority-based systems have been used to model the spread of fault to a certain vertex by checking for faults within a majority of its neighbors. Our focus is on irreversible majority processes wherein a vertex becomes permanently colored in a certain time period if at least half of its neighbors were in the colored state in the previous time period. We study such processes on planar, cylindrical, and toroidal triangular grid graphs. More specifically, we provide bounds for the minimum number of vertices in a dynamic monopolydefined as a set of vertices that, if initially colored, will result in the entire graph becoming colored in a finite number of time periods.
- Spread of fault; Spread of disease; Dynamic Monopoly; Dynamo; Triangular grid
Available at: http://works.bepress.com/sarah_spence_adams/21/
© 2012 Elsevier. This article was published in Discrete Applied Mathematics, vol. 160, iss. 10-11, pg. 1624-1633 and may be found here.