Skip to main content

Research Repository

Advanced Search

Simple dynamics on graphs

Gadouleau, Maximilien; Richard, Adrien

Simple dynamics on graphs Thumbnail


Authors

Adrien Richard



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 28, 2024
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

Files





You might also like



Downloadable Citations