Simple dynamics on graphs

Gadouleau, Maximilien; Richard, Adrien

Abstract

Can the interaction graph of a finite dynamical system force this system to have a “complex” dynamics? In other words, given a finite interval of integers A, which are the signed digraphs G such that every finite dynamical system f:An→An with G as interaction graph has a “complex” dynamics? If |A|≥3 we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph G there exists a system f:An→An with G as interaction graph that converges toward a unique fixed point in at most ⌊log2⁡n⌋+2 steps. The boolean case |A|=2 is more difficult, and we provide partial answers instead. We exhibit large classes of unsigned digraphs which admit boolean dynamical systems which converge toward a unique fixed point in polynomial, linear or constant time.

Citation

Gadouleau, M., & Richard, A. (2016). Simple dynamics on graphs. Theoretical Computer Science, 628, 62-77. https://doi.org/10.1016/j.tcs.2016.03.013

• Journal Article Type: Article
• Acceptance Date: Mar 8, 2016
• Online Publication Date: Mar 10, 2016
• Publication Date: Mar 10, 2016
• Deposit Date: Aug 26, 2016
• Publicly Available Date: Mar 10, 2017
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 628
• Pages: 62-77
• DOI: https://doi.org/10.1016/j.tcs.2016.03.013
• Public URL: https://durham-repository.worktribe.com/output/1377346