Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Update Sequence Stability In Graph Dynamical Systems, Matthew Macauley, Henning S. Mortveit
Update Sequence Stability In Graph Dynamical Systems, Matthew Macauley, Henning S. Mortveit
Publications
In this article, we study finite dynamical systems defined over graphs, where the functions are applied asynchronously. Our goal is to quantify and understand stability of the dynamics with respect to the update sequence, and to relate this to structural properties of the graph. We introduce and analyze three different notions of update sequence stability, each capturing different aspects of the dynamics. When compared to each other, these stability concepts yield vastly different conclusions regarding the relationship between stability and graph structure, painting a more complete picture of update sequence stability.
Cycle Equivalence Of Graph Dynamical Systems, Matthew Macauley, Henning S. Mortveit
Cycle Equivalence Of Graph Dynamical Systems, Matthew Macauley, Henning S. Mortveit
Publications
Graph dynamical systems (GDSs) generalize concepts such as cellular automata and Boolean networks and can describe a wide range of distributed, nonlinear phenomena. Two GDSs are cycle equivalent if their periodic orbits are isomorphic as directed graphs, which captures the notion of having comparable long-term dynamics. In this paper, we study cycle equivalence of GDSs in which the vertex functions are applied sequentially through an update sequence. The main result is a general characterization of cycle equivalence based on the underlying graph Y and the update sequences. We construct and analyse two graphs C(Y) and D( …