On Acyclic Orientations and Sequential Dynamical Systems |
| |
Authors: | C. M. Reidys |
| |
Affiliation: | Los Alamos National Laboratory, D 2, New Mexico, 87545, f1 |
| |
Abstract: | We study a class of discrete dynamical systems that consists of the following data: (a) a finite (labeled) graph Y with vertex set {1, …, n}, where each vertex has a binary state, (b) a vertex labeled multi-set of functions (Fi, Y: 2n → 2n)i, and (c) a permutation π Sn. The function Fi, Y updates the binary state of vertex i as a function of the states of vertex i and its Y-neighbors and leaves the states of all other vertices fixed. The permutation π represents a Y-vertex ordering according to which the functions Fi, Y are applied. By composing the functions Fi, Y in the order given by π we obtain the sequential dynamical system (SDS):Full-size image In this paper we first establish a sharp, combinatorial upper bound on the number of non-equivalent SDSs for fixed graph Y and multi-set of functions (Fi, Y). Second, we analyze the structure of a certain class of fixed-point-free SDSs. |
| |
Keywords: | acyclic orientations sequential dynamical system orderings graph automorphisms |
本文献已被 ScienceDirect 等数据库收录! |
|