Discrete and Continuous Dynamical Systems - Series S (DCDS-S)

Update sequence stability in graph dynamical systems

Pages: 1533 - 1541, Volume 4, Issue 6, December 2011      doi:10.3934/dcdss.2011.4.1533

       Abstract        References        Full Text (329.5K)       Related Articles

Matthew Macauley - Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, United States (email)
Henning S. Mortveit - Department of Mathematics, NDSSL, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, VA 24061, United States (email)

Abstract: 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 different conclusions regarding the relationship between stability and graph structure, painting a more complete picture of update sequence stability.

Keywords:  Asychronous update schedule, graph dynamical systems, stability, update sequence.
Mathematics Subject Classification:  Primary: 93D99, 37B99; Secondary: 05C90.

Received: May 2009;      Revised: November 2009;      Available Online: December 2010.