Periodic behavior of a diffusion model over directed graphs

We consider in this paper a discrete-time deterministic m-ary diffusion model over a strongly connected directed graph. The update rule is easy to state: let the vertices of the graph represent the agents and the edges represent the information flow; at every time step, each vertex updates its value to the maximum value held by its incoming neighbors at the last time step. The resulting system, defined over the graph, is a finite state machine, and hence, enters a periodic motion in finite time from any initial condition. We compute in this paper all possible periods of periodic motions of the system. In particular, by relating the periodic motions to directed cycles in the graph, we show that periods are common divisors of the lengths of the cycles, and vice versa.