Cycle Equivalence of Graph Dynamical Systems

Abstract

Graph dynamical systems (GDSs) can be used to describe a wide range of distributed, nonlinear phenomena. In this paper we characterize cycle equivalence of a class of finite GDSs called sequential dynamical systems SDSs. In general, two finite GDSs are cycle equivalent if their periodic orbits are isomorphic as directed graphs. Sequential dynamical systems may be thought of as generalized cellular automata, and use an update order to construct the dynamical system map. The main result of this paper is a characterization of cycle equivalence in terms of shifts and reflections of the SDS update order. We construct two graphs C(Y) and D(Y) whose components describe update orders that give rise to cycle equivalent SDSs. The number of components in C(Y) and D(Y) is an upper bound for the number of cycle equivalence classes one can obtain, and we enumerate these quantities through a recursion relation for several graph classes. The components of these graphs encode dynamical neutrality, the component sizes represent periodic orbit structural stability, and the number of components can be viewed as a system complexity measure.

References in corpus (2)

• On Enumeration of Conjugacy Classes of Coxeter Elements
• Equivalences on Acyclic Orientations

Cited by in corpus (7)

• On Enumeration of Conjugacy Classes of Coxeter Elements
• Equivalences on Acyclic Orientations
• Attractor Stability in Finite Asynchronous Biological System Models
• Bifurcations in Boolean Networks
• Adaptive Complex Contagions and Threshold Dynamical Systems
• Garden-of-Eden states and fixed points of monotone dynamical systems
• Posets from Admissible Coxeter Sequences