Additive Cellular Automata on Graphs (en Inglés) - Xiaoyan Zhang

This volume surveys the phenomenon of cellular automata, discrete dynamical systems consisting of an arrangement of basic components called cells together with a transition rule. The term was introduced by John von Neumann as a formal model for self-reproducing biological systems.

The authors of this volume highlight the study of automaton in biparte graphs and conduct an in-depth investigation into the minimum all-ones problem within the context of trees. While this problem is NP-hard for graphs, the authors manage to solve it in linear time when it comes to trees. They further present linear time algorithms for the minimum all-ones problem of unicyclic and bicyclic graphs.

Additionally, the authors study general all-ones problems for trees, and present all-colors problems on graphs. They go on to report on several variations of all-ones problems on graphs and on approximation algorithms for the minimum all-ones problem of arbitrary graphs. Throughout the volume, the authors list conjectures, open problems, and questions.

This volume proves inspirational for young graph theorists and graduate students to conduct further research and provide them with select proofs common in the study of cellular automata on graphs.