  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.
