2022/02/03 by Volker Turau, Turau, Volker · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Gene Regulatory Network Analysis #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2202.01580
openalex publication_date 2022/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper considers synchronous discrete-time dynamical systems on graphs based on the threshold model. It is well known that after a finite number of rounds these systems either reach a fixed point or enter a 2-cycle. The problem of finding the fixed points for this type of dynamical system is in general both NP-hard and #P-complete. In this paper we give a surprisingly simple graph-theoretic characterization of fixed points and 2-cycles for the class of finite trees. Thus, the class of trees is the first nontrivial graph class for which a complete characterization of fixed points exists. This characterization enables us to provide bounds for the total number of fixed points and pure 2-cycles. It also leads to an output-sensitive algorithm to efficiently generate these states.