Skip to main content

Research Repository

Advanced Search

Simple dynamics on graphs

Gadouleau, Maximilien; Richard, Adrien

Simple dynamics on graphs Thumbnail


Adrien Richard


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.


Gadouleau, M., & Richard, A. (2016). Simple dynamics on graphs. Theoretical Computer Science, 628, 62-77.

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


You might also like

Downloadable Citations