# Fixed Points and 2-Cycles of Synchronous Dynamic Coloring Processes on Trees

Volker Turau
Institute of Telematics
Hamburg University of Technology
21073 Hamburg, Germany
<EMAIL_ADDRESS>
###### Abstract

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.

##  1 Introduction

Synchronous discrete-time dynamical systems for information spreading received
a lot of attention in recent years. Often the following model is used: Let $G$
be a graph with an initial configuration, where each node is either black or
white. In discrete-time rounds, all nodes simultaneously update their color
based on a predefined local rule. The rule is local in the sense that the
color associated with a node in round $t$ is determined by the colors of the
neighboring nodes in round $t-1$. The main focus of the research so far has
been on the stabilization time of this process [21] and the dominance problem,
e.g., how many nodes must initially be black so that eventually all nodes are
black [17]. These questions have been considered for various classes of
graphs. These discrete-time dynamical systems are often based on the threshold
model. In a simple version of this model a node becomes black if at least a
fraction of $\alpha$ of its neighbors are black and white otherwise,
$\alpha\in(0,1)$ is a parameter of the model. In more elaborate versions edges
have weights and the local rules are based on the weighted fraction of
neighbors. The main property of these dynamical systems is that assuming
symmetric weights, the system has period $1$ or $2$ [10, 18]. This means that
such a system eventually reaches a stable configuration or it toggles between
two configurations. Fogelman et al. proved that the stabilization time is in
$O(n^{2})$ [7]. Frischknecht et al. showed that this bound is tight, up to
some poly-logarithmic factor [8].

In this paper we analyze a different aspect of discrete-time dynamical
systems: The number and structure of fixed points and 2-cycles. This research
is motivated by applications of so called Boolean networks (BN) [12], i.e.,
discrete-time dynamical systems, where each node (e.g., gene) takes either 0
(passive) or 1 (active) and the states of nodes change synchronously according
to regulation rules given as Boolean functions. An example for a regulation
rule is the majority rule, i.e., $\alpha=0.5$. Since the problem of finding
the fixed points of a BN is in general both NP-hard and #P-complete [3] (see
Sec. 2), it is interesting to find graph classes, for which the number of
fixed points can be determined efficiently. We regard our work as a step in
this direction. Interest in the set of fixed points of BNs was also sparked by
a result of Milano and Roli [14]. They use BNs to solve the satisfiability
problem (SAT) by defining a mapping between a SAT instance and a BN and prove
that BN fixed points correspond to SAT solutions.

This paper provides a characterization of the set of stable configurations
(a.k.a. fixed points) and the set of states of period $2$ (a.k.a. 2-cycles)
for a given finite tree based on its edge set. We do this for two versions of
the threshold model: minority and majority process. While the stabilization
times for the majority and minority process can differ considerably for a
given graph (see Fig. 1), the sets of stable configurations of a tree turn out
to be closely related for both process types. Our main contributions are as
follows:

  1. 1.

We identify a subset $E_{fix}(T)$ of the power set of the edge set of a tree
$T$ and show that the elements of $E_{fix}(T)$ correspond one-to-one with the
fixed points of $T$. $E_{fix}(T)$ is defined by a set of simple linear
inequalities over the node degrees. The fixed point corresponding to an
element of $E_{fix}(T)$ can be defined in simple terms. $E_{fix}(T)$ has the
hereditary property, i.e., if $X\in E_{fix}(T)$ then all subset of $X$ are
also elements of $E_{fix}(T)$. This property allows to define a simple output-
sensitive algorithm $\mathcal{A_{M}}$ to explicitly generate all fixed points.
This allows to prove upper bounds for the number of fixed points. We also show
that elements of $E_{fix}(T)$ correspond to solutions of a system of linear
diophantine inequalities.

  2. 2.

We characterize the configurations of period $2$, where each node changes its
color in every round (a.k.a. pure configurations). As above we identify a
subset $E_{pure}(T)$ of the power set of the edge set of $T$ such that the
elements of $E_{pure}(T)$ correspond one-to-one with the pure configurations
of $T$. As above the definition of $E_{pure}(T)$ is based on simple linear
inequalities and it has the hereditary property. The 2-cycle corresponding to
an element of $E_{pure}(T)$ is also defined in simple terms. Again this allows
to define a simple algorithm enumerating all 2-cycles and to prove upper
bounds for their number. Interestingly, $E_{pure}(T)$ is a subset of
$E_{fix}(T)$.

  3. 3.

Finally we look at general configurations with period $2$. We show that for
each configuration $c$ of this type each tree decomposes into subtrees, such
that $c$ induces either a fixed point or a pure configuration on each subtree.
The subtrees allow to define a hyper structure of a tree, called the block
tree. As in previous cases we identify a subset $E_{block}(T)$ of the power
set of the edge set of a tree $T$ and show that the elements of $E_{block}(T)$
correspond one-to-one with the block trees of $T$. $E_{block}(T)$ is a subset
of $E_{fix}(T)$. Since a tree can have several pure colorings, a block tree
does not uniquely define a coloring. We define a subclass of 2-cycles called
canonical colorings and prove that there is a direct correspondence between
$E_{block}(T)$ and canonical colorings. The characterization of $E_{block}(T)$
is not as simple as in the above cases, since $E_{block}(T)$ does not have the
hereditary property.

All results are obtained for the minority and the majority model.

##  2 State of the Art

Most research on discrete-time dynamical systems on graphs consecrates oneself
to bounds of the stabilization time. Good overviews for the majority resp. the
minority process can be found in [21] resp. [16]. Rouquier et al. study the
minority process in the asynchronous model, i.e., not all nodes update their
color concurrently [19]. They show that the stabilization time strongly
depends on the topology and observe that the case of trees is non-trivial.

The analysis of fixed points of the majority or minority process received only
some attention. Královič determined the number of fixed points of a complete
binary tree for the majority process [13]. Agur et al. did the same for ring
topologies [2]. In both cases the number of fixed points is an exponentially
small fraction of all configurations.

A related concept are Boolean networks, which have been extensively used as
mathematical models of genetic regulatory networks. The number of fixed points
of such a network is a key feature of its dynamical behavior. Boolean networks
have been extensively used as models for the dynamics of gene regulatory
networks. A gene is modeled by binary values, 0 or 1, indicating two
transcriptional states, either active or inactive, respectively. Each network
node operates by the same nonlinear majority rule, i.e., majority processes
are a particular type of BN [20]. The set of fixed points is an important
feature of the dynamical behavior of such networks [4]. The number of fixed
points is a measure for the general memory storage capacity of a system. Many
fixed points imply that a system can store a large amount of information, or,
in biological terms, has a large phenotypic repertoire [1]. However, the
problem of finding the fixed points of a Boolean network is in general both
NP-hard and #P-complete [3]. There are only a few theoretical results to
efficiently determine this set [11]. Aracena determined the maximum number of
fixed points in a particular class of BN called regulatory Boolean networks
[4].

Concepts related to fixed points of the minority resp. majority process have
been analyzed. A partition $(S,\bar{S})$ of the nodes of a graph is called a
global defensive $0$-alliance if $\lvert\mskip 0.90001muN_{S}(v)\mskip
0.90001mu\rvert\geq\lvert\mskip 0.90001muN_{\bar{S}}(v)\mskip 0.90001mu\rvert$
for each node $v$ [6]. Thus, a fixed point of the minority or majority process
induces a $0$-alliance, but the converse does not hold. The difference is that
no condition is placed on $v$. $0$-alliances are also called monopolies [15].

Mishra and Rao show that, for trees, a minimum monopoly can be computed in
linear time [15]. A related concept is that of $2$-community structure. Bazgan
et al. prove that each tree has a connected $2$-community structure and it can
be found in linear time [5].

##  3 Synchronous Discrete-Time Dynamical Systems

Let $G(V,E)$ be a finite, undirected graph. A coloring $c$ assigns to each
node of $G$ a value of $\\{0,1\\}$ with no further constraints on $c$. Denote
by $\mathcal{C}(G)$ the set of all colorings of $G$, i.e., $\lvert\mskip
0.90001mu\mathcal{C}(G)\mskip 0.90001mu\rvert=2^{\lvert\mskip 0.90001muV\mskip
0.90001mu\rvert}$. A transition process $\mathcal{M}$ describes the transition
of one coloring to another, i.e., it is a mapping
$\mathcal{M}:\mathcal{C}(G)\longrightarrow\mathcal{C}(G)$. Given an initial
coloring $c$, a transition process produces a sequence of colorings
$c,\mathcal{M}(c),\mathcal{M}(\mathcal{M}(c)),\ldots$. We consider two
transition processes: Minority and Majority process and denote the
corresponding mappings by $\mathcal{MIN}$ and $\mathcal{MAJ}$. They are local
mappings in the sense that the new color of a node is based on the current
colors of its neighbors. To determine $\mathcal{M}(c)$ the local mapping is
executed concurrently by all nodes. The transition from $c$ to
$\mathcal{M}(c)$ is called a round. In the minority (resp. majority) process
each node adopts the minority (resp. majority) color among all neighbors. In
case of a tie the color remains unchanged. Formally, the minority process is
defined for a node $v$ as follows:

$\mathcal{MIN}(c)(v)=\begin{cases}c(v)&\text{if }\lvert\mskip
0.90001muN^{c(v)}(v)\mskip 0.90001mu\rvert\leq\lvert\mskip
0.90001muN^{1-c(v)}(v)\mskip 0.90001mu\rvert\\\ 1-c(v)&\text{if }\lvert\mskip
0.90001muN^{c(v)}(v)\mskip 0.90001mu\rvert>\lvert\mskip
0.90001muN^{1-c(v)}(v)\mskip 0.90001mu\rvert\end{cases}$

$N^{i}(v)$ denotes the set of $v$’s neighbors with color $i$ ($i=0,1$). The
definition of $\mathcal{MAJ}$ is similar, only the binary operators $\leq$ and
$>$ are reversed. Sometimes a result holds for both processes. To simplify
matters in these cases we use the symbol $\mathcal{{M}}$ as a placeholder for
$\mathcal{{MIN}}$ and $\mathcal{{MAJ}}$. Fig. 1 depicts a sequence of
colorings for $\mathcal{{MIN}}$.

Figure 1: For the initial coloring on the left $\mathcal{{MIN}}$ reaches after
five rounds the coloring shown on the right. $\mathcal{{MAJ}}$ reaches for the
same initial coloring after one round a monochromatic coloring.

In this paper we are interested in colorings with specific properties. Let
$c\in\mathcal{C}(G)$. If $\mathcal{M}(c)=c$ then $c$ is called a fixed point.
It is called a 2-cycle if $\mathcal{M}(c)\not=c$ and
$\mathcal{M}(\mathcal{M}(c))=c$. A 2-cycle is called pure if
$\mathcal{M}(c)(v)\not=c(v)$ for each node $v$ of $G$. $c$ is called
monochromatic if all nodes have the same color, i.e., $c(v)=c(w)$ for all
$v,w\in V$. $c$ is called independent if the color of each node is different
from the colors of all its neighbors. Clearly, a monochromatic (resp.
independent) coloring is a fixed point for the majority (resp. minority)
process. An edge $(v,w)$ is called monochromatic for $c$ if $c(v)=c(w)$
otherwise it is called multi-chromatic.

For a mapping $\mathcal{M}$ denote by $\mathcal{F}_{\mathcal{M}}(G)$,
$\mathcal{C}^{2}_{\mathcal{M}}(G)$, and $\mathcal{P}_{\mathcal{M}}(G)$, the
set of all $c\in\mathcal{C}(G)$ that constitute a fixed point, a 2-cycle, or a
pure coloring for $\mathcal{M}$. If $c$ belongs to one of these sets the
complementary coloring and $\mathcal{M}(c)$ also belong to this set. To cope
with this fact we also define the sets $\mathcal{F}_{\mathcal{M}}(G)^{+}$,
$\mathcal{C}^{2}_{\mathcal{M}}(G)^{+}$, and $\mathcal{P}_{\mathcal{M}}(G)^{+}$
as the subsets of those colorings of the corresponding sets which assign to a
globally distinguished node $v^{\ast}$ color $0$. Hence, if
$c\in\mathcal{F}_{\mathcal{M}}(G)$ then either $c$ or the complement of $c$ is
in $\mathcal{F}_{\mathcal{M}}(G)^{+}$.

###  3.1 Notation

Let $T(V,E)$ be a finite, undirected tree with $n=\lvert\mskip
0.90001muV\mskip 0.90001mu\rvert$. For $F\subseteq E$ let $\mathcal{C}_{T}(F)$
be the set of connected components of $T\\!\setminus\\!F$. We define a tree
$\mathcal{T}_{F}$ with nodes ${\cal C}_{T}(F)$ and edges $F$. An edge of
$(u,w)\in F$ connects components $T_{1},T_{2}\in{\cal C}_{T}(F)$ if and only
if $u\in T_{1}$ and $w\in T_{2}$. For $F\subseteq E$ and $v\in V$ denote the
number of edges in $F$ incident to $v$ by $F_{v}$.

The nodes of a nontrivial tree $T$ can be uniquely partitioned into two
subsets, such that the nodes of each subset form an independent set. In the
following we denote these independent subsets by $\mathcal{I}_{0}(T)$ and
$\mathcal{I}_{1}(T)$. To enforce unambiguousness when dealing with these
subsets we demand that $v^{\ast}$ is contained in $\mathcal{I}_{0}(T)$. A star
graph is a tree with $n-1$ leaves. The maximal degree of a tree is denoted by
$\Delta$. We denote the $n^{th}$ Fibonacci number by $F_{n}$, i.e.,
$F_{0}=0,F_{1}=1$, and $F_{n}=F_{n-1}+F_{n-2}$. For a set $S$ we denote by
$\mathcal{P}(S)$ the power set of $S$, i.e., the set of all subsets of $S$.

##  4 Fixed Points

In this section we provide a characterization of
$\mathcal{F}_{\mathcal{M}}(T)$ with respect to subsets of $E$. In particular;
we identify a set $E_{fix}(T)\subset\mathcal{P}(E)$ and define a bijection
$\mathcal{B}_{fix}$ between $E_{fix}(T)$ and
$\mathcal{F}_{\mathcal{M}}(T)^{+}$. $E_{fix}(T)\not=\emptyset$ since
$\emptyset\in E_{fix}(T)$. This shows that every tree has at least one fixed
point. The definition of $\mathcal{B}_{fix}$ is different for $\mathcal{MIN}$
and $\mathcal{MAJ}$. These results allow to characterize the fixed points of
paths. In the second subsection we prove an upper bound for $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T)\mskip 0.90001mu\rvert$ in terms of $n$
and $\Delta$. For the case of paths we give the exact numbers. In the last
part we provide an output-sensitive algorithm to enumerate all fixed points.

###  4.1 The Bijection $\mathcal{B}_{fix}$

For $c\in\mathcal{F}_{\mathcal{MIN}}(T)$ nodes adjacent to edges monochromatic
for $c$ have degree at least two, moreover at most one half of the adjacent
edges of each node are monochromatic for $c$. Surprisingly the inverse of this
statement is also true and forms the basis for defining the bijection
$\mathcal{B}_{fix}$: If $F$ is a subset of the edges of $T$ such that nodes
adjacent to edges in $F$ have degree at least two and at most one half of the
adjacent edges of each node are in $F$ then $F$ uniquely defines a fixed point
of $\mathcal{F}_{\mathcal{M}}(T)$.

######  Lemma 1.

Let $T$ be a tree, $c\in\mathcal{F}_{\mathcal{M}}(T)$, and $F$ the set of
monochromatic (resp. multicolored) edges $(u,w)\in E$ if
$\mathcal{M}=\mathcal{MIN}$ (resp. $\mathcal{M}=\mathcal{MAJ}$). If $(u,w)\in
F$ then $deg_{T}(u)\geq 2$ and $deg_{T}(w)\geq 2$. Furthermore, $F_{v}\leq
deg_{T}(v)/2$ for each node $v$ of $T$.

###### Proof.

Assume $\mathcal{{M}}=\mathcal{{MIN}}$, the other case is proved similarly.
Then $\lvert\mskip 0.90001muN_{T}^{1-c(u)}(u)\mskip
0.90001mu\rvert\geq\lvert\mskip 0.90001muN_{T}^{c(u)}(u)\mskip
0.90001mu\rvert\geq 1$ for $(u,w)\in F$. Thus, $deg_{T}(u)=\lvert\mskip
0.90001muN_{T}^{c(u)}(u)\mskip 0.90001mu\rvert+\lvert\mskip
0.90001muN_{T}^{1-c(u)}(u)\mskip 0.90001mu\rvert\geq 2$. Similarly
$deg_{T}(w)\geq 2$. Let $v\in V$. Then $\lvert\mskip
0.90001muN_{T}^{c(v)}(v)\mskip 0.90001mu\rvert\leq\lvert\mskip
0.90001muN_{T}^{1-c(v)}(v)\mskip 0.90001mu\rvert$ since
$c\in\mathcal{F}_{\mathcal{M}}(T)$, i.e., $deg(v)\geq 2\lvert\mskip
0.90001muN_{T}^{c(v)}(v)\mskip 0.90001mu\rvert=2F_{v}$. ∎

The last lemma motivates the following definition of $E_{fix}(T)$. Note that
$E_{fix}(T)$ satisfies the hereditary property

######  Definition 2.

Let $T$ be a tree. $E^{2}(T)$ denotes the set of edges of $T$ where each end
node has degree at least two. $F\subseteq E^{2}(T)$ is called legal if
$F_{v}\leq deg(v)/2$ for each node $v$. $E_{fix}(T)$ denotes the set of all
legal subsets of a tree $T$.

######  Theorem 3.

For any tree $T$ there exists a bijection $\mathcal{B}_{fix}$ between
$E_{fix}(T)$ and $\mathcal{F}_{\mathcal{M}}(T)^{+}$.

###### Proof.

First assume $\mathcal{{M}}=\mathcal{{MIN}}$. Let $F\in E_{fix}(T)$. We define
a coloring $c_{F}\in\mathcal{F}_{\mathcal{MIN}}(T)$. Let
$T^{\ast}\in\mathcal{C}_{T}(F)$ with $v^{\ast}\in T^{\ast}$. Let
$c_{F}(v^{\ast})=0$ and extend $c_{F}$ to an independent coloring of
$T^{\ast}$, e.g., by using breadth-first search. This uniquely defines $c_{F}$
on $T^{\ast}$. We extend $c_{F}$ successively to a coloring with
$c_{F}\in\mathcal{F}_{\mathcal{MIN}}(T)^{+}$. While there exists an already
colored node $u$ that has an uncolored neighbor do the following. Let
$T_{1}\in\mathcal{C}_{T}(F)$ with $u\in T_{1}$, $N_{1}=N_{T_{1}}(u)$, and
$N_{2}=N_{T}(u)\setminus N_{1}$. All nodes in $N_{1}$ have color $1-c_{F}(u)$
and $F_{u}=\lvert\mskip 0.90001muN_{2}\mskip 0.90001mu\rvert$. No node of
$N_{2}$ has yet been assigned a color. By assumption we have $\lvert\mskip
0.90001muN_{2}\mskip 0.90001mu\rvert\leq deg_{T}(u)/2$. Hence, $\lvert\mskip
0.90001muN_{2}\mskip 0.90001mu\rvert\leq\lvert\mskip 0.90001muN_{1}\mskip
0.90001mu\rvert$. Set $c_{F}(w)=c_{F}(u)$ for all $w\in N_{2}$. For each $w\in
N_{2}$ let $T_{w}\in\mathcal{C}_{T}(F)$ with $w\in T_{w}$. Extend $c_{F}$ to
an independent coloring on each $T_{w}$. Then $\lvert\mskip
0.90001muN_{T}^{c_{F}(u)}\mskip 0.90001mu\rvert\leq\lvert\mskip
0.90001muN_{T}^{1-c_{F}(u)}\mskip 0.90001mu\rvert$. Clearly this uniquely
defines $c_{F}$ and $c_{F}\in\mathcal{F}_{\mathcal{MIN}}(T)^{+}$. Now we can
define $\mathcal{B}_{fix}(F)={c}_{F}\text{ for each }F\in E_{fix}(T)$. Let
$F_{1}\not=F_{2}\in E_{fix}(T)$ and $e=(u,w)\in F_{1}\setminus F_{2}$. Then
$c_{F_{1}}(w)=c_{F_{1}}(u)$ and $c_{F_{2}}(w)\not=c_{F_{2}}(u)$. Hence,
$c_{F_{1}}\not=c_{F_{2}}$. Thus, $\mathcal{B}_{fix}(F)$ is injective.

Next, we prove that $\mathcal{B}_{fix}$ is surjective, i.e., for every
$c\in\mathcal{F}_{\mathcal{MIN}}(T)^{+}$ there exists $F_{c}\in E_{fix}(T)$
such that $\mathcal{B}_{fix}(F_{c})=c$. For
$c\in\mathcal{F}_{\mathcal{MIN}}(T)^{+}$ let $F_{c}=\\{(u,w)\in
E\;|\;c(u)=c(w)\\}$. Then $F_{c}\in E_{fix}(T)$ by Lemma 1. By the first part
of this proof we have
$\mathcal{B}_{T}(F_{c})\in\mathcal{F}_{\mathcal{MIN}}(T)^{+}$. Let $v\in
T^{\ast}$ and $u\in N_{T^{\ast}}(v)$. Then $c(u)\not=c(v)$, otherwise
$u\not\in T^{\ast}$. Hence, $\mathcal{B}_{T}(F_{c})$ is for $T^{\ast}$
independent. Since $c_{F_{c}}(v^{\ast})=c(v^{\ast})=0$ we have
$\mathcal{B}_{T}(F_{c})(v)=c(v)$ for all $v\in T^{\ast}$. Next we repeat this
argument for all $\hat{T}\in{\cal C}_{T}(F_{c})$. Thus, $c$ and
$\mathcal{B}_{T}(F_{c})$ define the same coloring of $T$, i.e.,
$\mathcal{B}_{T}(F_{c})=c$.

Next assume $\mathcal{{M}}=\mathcal{{MAJ}}$. Let $F\in E_{fix}(T)$. We use the
partition of the nodes of $\mathcal{T}_{F}$ into two independent subsets
$\mathcal{I}_{0}$ and $\mathcal{I}_{1}$ to define a mapping $C_{F}:{\cal
C}_{T}(F)\rightarrow\\{0,1\\}$ by setting $C_{F}(\hat{T})=i$ if
$\hat{T}\in\mathcal{I}_{i}$ for $i=0,1$. We define a coloring $c_{F}$ of $T$
as follows

$c_{F}(v)=C_{F}(\hat{T})\text{ if }v\in\hat{T}.$

$F$ uniquely defines $c_{F}$ among all colorings with $c_{F}(v^{\ast})=0$,
since $v^{\ast}\in T^{\ast}\in\mathcal{I}_{0}$. First, we prove that
${c}_{F}\in\mathcal{F}_{\mathcal{MAJ}}(T)^{+}$. For $v\in V$ let
$\hat{T}\in{\cal C}_{T}(F)$ with $v\in\hat{T}$. Then
$N(v)\cap\hat{T}=N_{T}^{c_{F}(v)}(v)$ and $F_{u}=\lvert\mskip
0.90001muN_{T}^{1-c_{F}(v)}(v)\mskip 0.90001mu\rvert$. Since $F\in E_{fix}(T)$
we have $\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip 0.90001mu\rvert\geq
deg(v)/2$. Thus, $2\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip
0.90001mu\rvert\geq\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip
0.90001mu\rvert+\lvert\mskip 0.90001muN_{T}^{1-c_{F}(v)}(v)\mskip
0.90001mu\rvert$ and hence, $\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip
0.90001mu\rvert\geq\lvert\mskip 0.90001muN_{T}^{1-c_{F}(v)}(v)\mskip
0.90001mu\rvert$. Thus, no node can change its color. i.e.,
$c_{F}\in\mathcal{F}_{\mathcal{MAJ}}(T)^{+}$. Now we define

$\mathcal{B}_{fix}(F)={c}_{F}\text{ for each }F\in E_{fix}(T).$

As in the proof for $\mathcal{{M}}=\mathcal{{MIN}}$ we can show that
$\mathcal{B}_{fix}(F)$ is injective.

Next, we prove that $\mathcal{B}_{fix}$ is surjective, i.e., for every
$c\in\mathcal{F}_{\mathcal{MAJ}}(T)^{+}$ there exists $F_{c}\in E_{fix}(T)$
such that $\mathcal{B}_{fix}(F_{c})=c$. For
$c\in\mathcal{F}_{\mathcal{MAJ}}(T)^{+}$ define $F_{c}=\\{(u,w)\in
E\;|\;c(u)\not=c(w)\\}$. Let $(u,w)\in F_{c}$. Then $F_{c}\in E_{fix}(T)$ by
Lemma 1. By the first part of this proof we have
$\mathcal{B}_{fix}(F_{c})\in\mathcal{F}_{\mathcal{MAJ}}(T)^{+}$.

Let $v\in T^{\ast}$ and $u\in N_{T^{\ast}}(v)$. Then $c(u)=c(v)$, otherwise
$u\not\in T^{\ast}$. Hence, $\mathcal{B}_{fix}(F_{c})$ is for
$T^{\ast}\in{\cal C}_{T}(F_{c})$ monochromatic. Since
$c_{F_{c}}(v^{\ast})=c(v^{\ast})=0$ we have $\mathcal{B}_{fix}(F_{c})(v)=c(v)$
for all $v\in T^{\ast}$. Now we repeat this argument for all $\hat{T}\in{\cal
C}_{T}(F_{c})$. Thus, $c$ and $\mathcal{B}_{fix}(F_{c})$ define the same
coloring, i.e., $\mathcal{B}_{fix}(F_{c})=c$. ∎

Theorem 3 implies the following two results.

######  Corollary 4.

Let $T$ be a tree. The minority process has an independent fixed point. It has
a non-independent fixed point if and only if $T$ has at least two inner nodes.
The majority process has a monochromatic fixed point. It has a non-
monochromatic fixed point if and only if $T$ has at least two inner nodes.

###### Proof.

Since $\emptyset\in E_{fix}(T)$ we have
$c_{\emptyset}\in\mathcal{F}_{\mathcal{MIN}}(T)$ and $c_{\emptyset}$ is an
independent coloring. By Theorem 3 $T$ has a non-independent fixed point if
and only if $E_{fix}(T)\not=\emptyset$. This is equivalent to having at least
two inner nodes. The proof for $\mathcal{MAJ}$ is similar. ∎

######  Corollary 5.

A coloring of a path is a fixed point of the minority (resp. majority) process
if and only if each node has at least one neighbor with a different (resp.
same) color.

###### Proof.

Let $P_{n}$ be a path and $F\in E_{fix}(P_{n})$. If $n\leq 3$ then
$E_{fix}(T)=\emptyset$, i.e., $\mathcal{F}_{\mathcal{MIN}}(P_{n})$ (resp.
$\mathcal{F}_{\mathcal{MAJ}}(P_{n})$) consist of the two independent (resp.
monochromatic) colorings. Let $n\geq 4$. Then $F$ is a matching of $P_{n-2}$
since the end edges of $P_{n}$ cannot be in $F$. Since $c_{F}$ induces an
independent (resp. monochromatic) coloring for every $\hat{T}\in{\cal
C}_{T}(F)$ and $\lvert\mskip 0.90001mu\hat{T}\mskip 0.90001mu\rvert\geq 2$ the
proof is complete. ∎

###  4.2 Counting Fixed Points

Theorem 3 allows to compute the number of fixed points in specific cases. If
$\Delta=n-1$ (resp. $\Delta=n-2$) then $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{MIN}}(T)\mskip 0.90001mu\rvert=2$ (resp.
$\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{MIN}}(T)\mskip
0.90001mu\rvert=4$). Furthermore, $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{MIN}}(T)\mskip 0.90001mu\rvert\leq 8$ if
$\Delta=n-3$. To get more general results we describe an algorithm
$\mathcal{A_{M}}$ to generate all fix points of a given tree $T$. We start
with node $v^{\ast}$ and color it with $0$. Algorithm $\mathcal{A_{M}}$ is
recursive and extends a partial coloring by coloring all uncolored neighbors
of an already colored node. In this context a partial coloring is a coloring
of a subset of the nodes of $T$ with the following property: Let $v$ be an
already colored node. Firstly, all nodes on the path from $v^{\ast}$ to $v$ in
$T$ are also colored. Secondly, if a neighbor of $v$ other than the one closer
to $v^{\ast}$ is colored, then all neighbors of $v$ are colored.

The details of a recursive call for the minority process, i.e.,
$\mathcal{A_{MIN}}$ are as follows. Given a partial coloring $c$, a single
invocation generates several extensions of $c$, all of them are again partial
colorings covering more nodes. Let $v$ be an already colored node that has an
uncolored neighbor. First, each uncolored neighbor of $v$ that is a leaf gets
the complementary color of $v$. Then $v$ has $r=deg(v)-\lvert\mskip
0.90001muN^{0}(v)\mskip 0.90001mu\rvert-\lvert\mskip 0.90001muN^{1}(v)\mskip
0.90001mu\rvert$ uncolored neighbors. Let $U$ be the set of the uncolored
neighbors of $v$, note none of them is a leaf. We color $\hat{N}_{0}$ (resp.
$\hat{N}_{1}$) of these $r$ neighbors with color $0$ (resp. $1$), i.e.,
$r=\hat{N}_{0}+\hat{N}_{1}$. In order to produce a fixed point the following
inequality must be satisfied:

$\lvert\mskip 0.90001muN^{c(v)}(v)\mskip
0.90001mu\rvert+\hat{N}_{c(v)}\leq\lvert\mskip 0.90001muN^{1-c(v)}(v)\mskip
0.90001mu\rvert+\hat{N}_{1-c(v)}=\lvert\mskip 0.90001muN^{1-c(v)}(v)\mskip
0.90001mu\rvert+r-\hat{N}_{c(v)}.$

Hence,

$\hat{N}_{c(v)}\leq\frac{r+\lvert\mskip 0.90001muN_{1-c(v)}(v)\mskip
0.90001mu\rvert-\lvert\mskip 0.90001muN_{c(v)}(v)\mskip 0.90001mu\rvert}{2}.$
(1)

Let

$r_{0}=\min\left(\lfloor(r+\lvert\mskip 0.90001muN_{1-c(v)}(v)\mskip
0.90001mu\rvert-\lvert\mskip 0.90001muN_{c(v)}(v)\mskip
0.90001mu\rvert)/2\rfloor,r\right).$ (2)

For $i=0,\ldots,r_{0}$ we extend $c$ by coloring a subset $S$ of $U$ of size
$i$ with color $c(v)$ and the remaining nodes $U\setminus S$ with color
$c(v)-1$. This way we get $\sum_{i=0}^{r_{0}}\binom{r}{i}$ extended partial
colorings. $\mathcal{A_{MIN}}$ is applied to each of these extensions and
terminates when all nodes are colored. Clearly, the resulting colorings are
fixed points and all fixed points are generated this way. Algorithm
$\mathcal{A_{MAJ}}$ differs only in two places. Firstly, uncolored neighbors
of $v$ that are leaves gets the same color as $v$. Secondly, in Eq. (1)
operator $\geq$ must be replaced by $\leq$ and the assignment of colors to
nodes in $U$ is reversed.

Next we prove an upper bound for $\lvert\mskip
0.90001mu{F}_{\mathcal{{M}}}(T)\mskip 0.90001mu\rvert$. According to Corollary
4 each tree has at least two fixed points. A star graph is an extreme case,
because it only has two fixed points. The other extreme are paths as shown in
this section. We start with a simple observation.

######  Lemma 6.

Let $T$ be a tree with a path $v_{0},v_{1},v_{2},v_{3}$ such that
$deg(v_{0})=1$ and $deg(v_{1})=deg(v_{2})=2$. Let $T^{0}=T\setminus v_{0}$ and
$T^{1}=T^{0}\setminus v_{1}$. Then $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T)\mskip 0.90001mu\rvert=\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T^{0})\mskip 0.90001mu\rvert+\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T^{1})\mskip 0.90001mu\rvert$.

###### Proof.

We assume $\mathcal{{M}}=\mathcal{{MIN}}$, the other case is proved similarly.
Note that for each $c\in\mathcal{F}_{\mathcal{{M}}}(T)$, the color of $v_{0}$
is determined by that of $v_{1}$, i.e., $c(v_{0})=1-c(v_{1})$. We apply the
above described algorithm $\mathcal{A_{\mathcal{MIN}}}$ to $T^{1}$ and
$T^{0}$, where vertices $v_{2},v_{1}$ and $v_{0}$ are visited last and in this
order. We classify the fixed points $c$ of $T$ in two categories:
$\mathcal{F}_{=}$ consists of those $c$ with $c(v_{2})=c(v_{1})$ and
$\mathcal{F}_{\not=}$ the remaining colorings. Colorings of
$\mathcal{F}_{\not=}$ arise when $\mathcal{A_{\mathcal{MIN}}}$ is applied to
$T^{0}$, because $v_{1}$ is a leaf in $T^{0}$ and therefore $v_{1}$ and
$v_{2}$ do receive different colors for $T^{0}$. Thus, each fixed point
$c\in\mathcal{F}_{\not=}$ of this category can be uniquely paired with a fixed
point of $T_{0}$, by setting $c(v_{0})=1-c(v_{1})$. Consider an application of
$\mathcal{A_{\mathcal{MIN}}}$ to $T^{1}$. Since $v_{2}$ is a leaf in $T^{1}$,
$v_{2}$ and $v_{3}$ receive different colors. Thus, these colorings are
uniquely extended to $T$ by setting $c(v_{1})=c(v_{2})$ and
$c(v_{0})=1-c(v_{1})$. Hence, fixed points of $T^{1}$ can be uniquely paired
with fixed points of $\mathcal{F}_{=}$. Since we have associated each fixed of
$T$ with a fixed point of either $T^{0}$ or $T^{1}$ we have $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{MIN}}(T)\mskip 0.90001mu\rvert=\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{MIN}}(T^{0})\mskip 0.90001mu\rvert+\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{MIN}}(T^{1})\mskip 0.90001mu\rvert$. ∎

Before proving Theorem 8 we provide a technical result.

######  Lemma 7.

Let $T$ be a tree and $v$ a leaf of $T$ with neighbor $w$. Let $n_{l}$ (resp.
$n_{i}$) be the number of neighbors of $w$ that are leaves (resp. inner
nodes). If $n_{l}>n_{i}$ then there is a one-to-one correspondence between
$\mathcal{F}_{\mathcal{{M}}}(T)$ and $\mathcal{F}_{\mathcal{{M}}}(T\setminus
v)$.

###### Proof.

For $c\in\mathcal{F}_{\mathcal{{M}}}(T)$ the children of $w$ that are leaves
are colored with $c(w)$ if $\mathcal{{M}}=\mathcal{{MAJ}}$ and with $1-c(w)$
otherwise. Thus, if $c_{1},c_{2}\in\mathcal{F}_{\mathcal{{M}}}(T)$ with
$c_{1}(u)=c_{2}(u)$ for all $u\not=v$ then $c_{1}=c_{2}$. Hence, $c$ uniquely
corresponds to an element of $\mathcal{F}_{\mathcal{{M}}}(T\setminus v)$.
Consider the coloring of $w$’s children by $\mathcal{A_{\mathcal{M}}}$. Since
$n_{l}>n_{i}$ an arbitrary number of the non-leaf neighbors of $w$ can receive
color $c(w)$ (resp. $1-c(w)$. If one of $w$’s leaf children is removed, $w$
still has at least as many leaf children as non-leaf children. Hence,
$\mathcal{A_{\mathcal{M}}}$ produces the same fixed points. ∎

A path of length $3$ shows that the last lemma does not hold in case
$n_{l}=n_{i}$.

######  Theorem 8.

Let $T$ be a tree and $P$ a path. Then $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T)\mskip 0.90001mu\rvert\leq
2F_{n-\lceil\Delta/2\rceil}$ and $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(P)\mskip 0.90001mu\rvert=2F_{n-1}$.

###### Proof.

We assume $\mathcal{{M}}=\mathcal{{MIN}}$, the other case is proved similarly.
The proof is by induction on $n$. If $\Delta=2$ the result holds by Theorem 8.
If $T$ is a star graph then $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{MIN}}}(T)\mskip 0.90001mu\rvert=2$, again the
result is true. Let $\Delta>2$ and $T$ not a star graph. Thus, $n>4$. Let
$\tilde{E}$ be the set of edges $(v,w)$ of $T$ where $v$ is a leaf and all
neighbors of $w$ but one are leaves. Then $\lvert\mskip
0.90001mu\tilde{E}\mskip 0.90001mu\rvert\geq 2$ since $T$ is not a star graph.
Thus, there exits $(v,w)\in\tilde{E}$ such that there exists a node different
from $w$ that has degree $\Delta$. If $deg(w)>2$ then there exists a neighbor
$u\not=v$ of $w$ that is a leaf. Let $T_{u}=T\setminus u$. Then $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T)\mskip 0.90001mu\rvert=\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T_{u})\mskip 0.90001mu\rvert$ by Lemma 7.
Thus, the result is true by induction since $\Delta(T_{u})=\Delta(T)$.

Hence, we can assume that $deg(w)=2$. Let $u\not=v$ be the second neighbor of
$w$. Denote by $T_{v}$ (resp. $T_{w}$) the tree $T\setminus v$ (resp.
$T\setminus\\{v,w\\}$). Assume that $u$ is the only node in $T$ with degree
$\Delta$. Repeating the above argument proves that $T$ is an extended star
graph with center node $u$ and that all neighbors of $u$ have degree $1$ or
$2$. Applying algorithm $\mathcal{A_{MIN}}$ shows that the largest number of
fixed points is achieved if all $\Delta$ neighbors of $u$ have degree $2$.
Then $n=2\Delta+1$, $r=\Delta$ and $r_{0}=\lfloor\Delta/2\rfloor$ by Eq. (2).
If $\Delta\equiv 0(2)$ then as shown above

$\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{{M}}}(T)\mskip
0.90001mu\rvert=2\sum_{i=0}^{\Delta/2}\binom{\Delta}{i}=2^{\Delta}+\binom{\Delta}{\Delta/2}\leq
2F_{3\Delta/2+1}=2F_{n-\lceil\Delta/2\rceil}.$

The case $\Delta\equiv 1(2)$ is proved similarly. Therefore, we can assume
that $T_{w}$ contains a node with degree $\Delta$. Thus, by induction:
$2F_{n-1-\lceil\Delta/2\rceil}\geq\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T_{v})\mskip 0.90001mu\rvert$ and
$2F_{n-2-\lceil\Delta/2\rceil}\geq\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{{M}}}(T_{w})\mskip 0.90001mu\rvert$.

Denote by $\mathcal{F}_{=}$ (resp. $\mathcal{F}_{\not=}$) the set of fixed
points $c$ of $T$ with $c(u)=c(w)$ (resp. $c(u)\not=c(w)$). Note that
$c(v)=1-c(w)$. If $c\in\mathcal{F}_{\not=}$ then $c\in{\cal
F}_{\mathcal{{M}}}(T_{v})$ and if $c\in\mathcal{F}_{=}$ then $c\in{\cal
F}_{\mathcal{{M}}}(T_{w})$. Hence,

$\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{{M}}}(T)\mskip
0.90001mu\rvert=\lvert\mskip 0.90001mu\mathcal{F}_{\not=}\mskip
0.90001mu\rvert+\lvert\mskip 0.90001mu\mathcal{F}_{=}\mskip
0.90001mu\rvert\leq
2F_{n-1-\lceil\Delta/2\rceil}+2F_{n-2-\lceil\Delta/2\rceil}=2F_{n-\lceil\Delta/2\rceil}.$

∎

Fig. 2 shows that the bound of Theorem 8 is not sharp. Let $B_{h}$ be a binary
tree of depth $h$. The equation

$\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{M}}(B_{h})\mskip
0.90001mu\rvert=\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{M}}(B_{h-1})\mskip
0.90001mu\rvert(\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{M}}(B_{h-1})\mskip
0.90001mu\rvert+2\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{M}}(B_{h-2})\mskip 0.90001mu\rvert^{2})$

already contained in [13] directly follows from Theorem 3.

Figure 2: Three trees with five nodes having 4, 2, and 6 fixed points for
$\mathcal{MIN}$.

###  4.3 Generating Fixed Points

The fixed points of a tree $T$ can be generated by iterating over all subsets
of $E^{2}(T)$ and outputting the legal ones. The algorithm exploits the fact
that $E_{fix}(T)$ has the hereditary property, i.e., if $X\in E^{2}(T)$ is
legal, all subset of $X$ are also legal. Algorithm 1 describes an output-
sensitive algorithm running in time $O(n+\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert\times\lvert\mskip
0.90001muE^{2}(T)\mskip 0.90001mu\rvert)$. Since $\lvert\mskip
0.90001muE^{2}(T)\mskip 0.90001mu\rvert\leq n$ the running time is in
$O(n\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip
0.90001mu\rvert)$. If $E^{2}(T)=\\{e_{1},\ldots,e_{l}\\}$ then the algorithm
successively constructs the set of all legal subsets using the edges
$\\{e_{1},\ldots,e_{i}\\}$ for $i=0,\ldots,l$. The inner foreach-loop always
iterates over the list fixedPoints beginning at the first entry.

input : A tree $T=(V,E)$

$E^{2}:=\\{(u,w)\in E\;|\;deg(u)\geq 2\text{ and }deg(w)\geq 2\\}$;

$\mathrm{fixedPoints}:=\emptyset$; $\mathrm{fixedPoints.append}(\emptyset)$;

foreach $e\in E^{2}$ do

$\mathrm{count}:=\mathrm{fixedPoints.size}()$;

foreach $\mathrm{X}\in\mathrm{fixedPoints}$ do

if $\\{e\\}\cup\mathrm{X}\text{ is legal}$ then

$\mathrm{fixedPoints.append}(\mathrm{\\{e\\}\cup\mathrm{X}})$;

$\mathrm{count}:=\mathrm{count}-1$;

if $\mathrm{count}==0$ then

break ;

return $\mathrm{fixedPoints}$;

Algorithm 1 Algorithm to generate a list of all fixed points of a tree
$T(V,E)$

######  Theorem 9.

Algorithm 1 computes all $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$ fixed points of a
tree $T$ in time $O(n+\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip
0.90001mu\rvert\times\lvert\mskip 0.90001muE^{2}(T)\mskip 0.90001mu\rvert)$
using $O(\lvert\mskip 0.90001muE^{2}(T)\mskip
0.90001mu\rvert\times\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip
0.90001mu\rvert)$ memory.

###### Proof.

By Theorem 3 each legal subset of $E^{2}(T)$ uniquely corresponds to a fixed
point of $T$. If a subset $S$ of $E^{2}(T)$ is not legal, then no superset of
$S$ is legal and if $S$ is legal then all subsets of $S$ are legal. Therefore,
the algorithm generates all legal subsets of $E^{2}(T)$. Let $l=\lvert\mskip
0.90001muE^{2}(T)\mskip 0.90001mu\rvert$. Denote by $S_{i}$ the set of
elements of the list $fixedPoints$ at the beginning of the $i^{th}$ outer
foreach-loop and $S_{l+1}$ the elements of $fixedPoints$ after the last
execution. Then $\lvert\mskip 0.90001muS_{1}\mskip 0.90001mu\rvert=1$ and
$\lvert\mskip 0.90001mu\mathcal{F}(T)^{+}\mskip 0.90001mu\rvert=\lvert\mskip
0.90001muS_{l+1}\mskip 0.90001mu\rvert$.

Next we prove that $(4/5)\lvert\mskip 0.90001muS_{i+1}\mskip
0.90001mu\rvert\geq\lvert\mskip 0.90001muS_{i}\mskip 0.90001mu\rvert$ for
$i=1,\ldots,l$. Let $e=(u,w)\in E^{2}(T)$. For $X\in S_{i}$ denote the number
of edges in $X$ that are incident with a node $v$ by $X_{v}$. Let
$\bar{S}=S_{i}$ and $\hat{S}=\emptyset$. Let $X\in\bar{S}$ with
$X_{u}+1>deg(u)/2$ and $X_{w}+1>deg(w)/2$. Let $e_{u}$ (resp. $e_{w}$) be an
edge of $X$ that is incident with $u$ (resp. $w$). Then we remove
$X,X\setminus\\{e_{u},e_{w}\\},X\setminus\\{e_{u}\\}$, and
$X\setminus\\{e_{w}\\}$ from $\bar{S}$ and insert
$X,X\setminus\\{e_{u},e_{w}\\},X\setminus\\{e_{u}\\}$,
$X\setminus\\{e_{w}\\}$, and $X\setminus\\{e_{u},e_{w}\\}\cup\\{e\\}$ into
$\hat{S}$. We repeat this process until there is no $X$ in $\bar{S}$ with the
above property. Next, let $X\in\bar{S}$ with $X_{u}+1>deg(u)/2$ and
$X_{w}+1\leq deg(w)/2$. Let $e_{u}$ be an edge of $X$ that is incident with
$u$. Then we remove $X$, and $X\setminus\\{e_{u}\\}$ from $\bar{S}$ and insert
$X,X\setminus\\{e_{u}\\},X\setminus\\{e_{u}\\}\cup\\{e\\}$ into $\hat{S}$. We
repeat this process until there is no $X$ in $\bar{S}$ with the above
property. Finally, for the remaining $X\in\bar{S}$ we insert $X,X\cup\\{e\\}$
into $\hat{S}$. Assume, that $S_{i}$ contains $n_{1},n_{2}$ resp. $n_{3}$
elements according to the above classification, then

$\lvert\mskip 0.90001muS_{i}\mskip 0.90001mu\rvert=4n_{1}+2n_{2}+n_{3}\text{
and }\lvert\mskip 0.90001mu\hat{S}\mskip
0.90001mu\rvert=5n_{1}+3n_{2}+2n_{3}.$

Since $S_{i+1}=\hat{S}$ we have $(4/5)\lvert\mskip 0.90001muS_{i+1}\mskip
0.90001mu\rvert\geq\lvert\mskip 0.90001muS_{i}\mskip 0.90001mu\rvert$. The
overall number of executions of the inner foreach-loop is
$\sum_{i=1}^{l}\lvert\mskip 0.90001muS_{i}\mskip 0.90001mu\rvert$. Thus,

$\sum_{i=1}^{l}\lvert\mskip 0.90001muS_{i}\mskip
0.90001mu\rvert\leq(4/5)\sum_{i=2}^{l+1}\lvert\mskip 0.90001muS_{i}\mskip
0.90001mu\rvert=(4/5)\sum_{i=1}^{l}\lvert\mskip 0.90001muS_{i}\mskip
0.90001mu\rvert+(4/5)(\lvert\mskip 0.90001muS_{l+1}\mskip 0.90001mu\rvert-1).$

Hence,

$\sum_{i=1}^{l}\lvert\mskip 0.90001muS_{i}\mskip 0.90001mu\rvert\leq
4(\lvert\mskip 0.90001muS_{l+1}\mskip 0.90001mu\rvert-1)<4\lvert\mskip
0.90001mu\mathcal{F}(T)^{+}\mskip 0.90001mu\rvert.$

In time $O(n)$ we provide the degrees of all nodes in an array. Also the test
whether $X\cup e$ is legal and append the entry to the list can be performed
in time $O(\lvert\mskip 0.90001muX\mskip 0.90001mu\rvert)$. ∎

The bound $(4/5)\lvert\mskip 0.90001muS_{i+1}\mskip
0.90001mu\rvert\geq\lvert\mskip 0.90001muS_{i}\mskip 0.90001mu\rvert$ for all
$i$ can be used to prove the lower bound of $((5/4)^{l}$ with $l=\lvert\mskip
0.90001muE^{2}(T)\mskip 0.90001mu\rvert$ for $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$. We conjecture
that a more detailed analysis of the relation between $\lvert\mskip
0.90001muS_{i+1}\mskip 0.90001mu\rvert$ and $\lvert\mskip 0.90001muS_{i}\mskip
0.90001mu\rvert$ leads to a better bound.

Finally, we sketch an alternative approach for computing all fixed points. The
elements of $E_{fix}(T)$ correspond to the solutions of a system of linear
diophantine inequalities $Ax\leq b$. Here, $A$ is a binary $\lvert\mskip
0.90001muE^{2}(T)\mskip 0.90001mu\rvert\times n$ matrix, where $a_{i,j}=1$ if
node $i$ is incident with edge $j$ of $E^{2}(T)$ and $b_{i}=\lfloor
deg_{T}(i)/2\rfloor$. Thus, by Theorem 3 the set of fixed points corresponds
to the solutions of $Ax\leq b$. Unfortunately there isn’t much work available
for solving systems of linear diophantine inequalities [9].

##  5 General 2-Cycles

In this section we analyze the structure of
$\mathcal{C}^{2}_{\mathcal{M}}(T)$. First we collect general results about
colorings from $\mathcal{C}^{2}_{\mathcal{MIN}}(T)$. In the second subsection
we consider the set $c\in\mathcal{P}_{\mathcal{M}}(T)$ of all pure colorings.
We first prove properties of $c$ and use these to define the set $E_{pure}(T)$
and define a bijection $\mathcal{B}_{pure}$ between $E_{pure}(T)$ and
$\mathcal{P}_{\mathcal{M}}(T)^{+}$. Since $E_{pure}(T)\not=\emptyset$ this
shows that every tree has pure coloring. These results immediately lead to a
simple characterization pure coloring of paths. In the third subsection we
derive from $\mathcal{B}_{pure}$ an upper bound for $\lvert\mskip
0.90001mu\mathcal{P}_{\mathcal{{M}}}(T)\mskip 0.90001mu\rvert$ in terms of
$n$. Finally we consider the general case of 2-cycles. We prove that $T$
decomposes into subtrees, such that $c$ is either a fixed point or a pure
coloring on each of these subtrees. These subtrees provide the basis to define
a hyper structure of a tree, called the block tree. After analyzing properties
of block trees we define a set $E_{block}(T)$ of subsets of the edge set of a
tree $T$ and show in Theorem 29 that the elements of $E_{block}(T)$ correspond
one-to-one with the block trees of $T$. Since $E_{block}(T)$ does not have the
hereditary property, we cannot use the approach of Algorithm 1 to enumerate
all block trees.

###  5.1 General Results

Let $c\in\mathcal{C}^{2}_{\mathcal{M}}(T)$. We separate the nodes of $T$ in
two groups. A node $u$ is called a fixed node for $c$ if
$\mathcal{M}(c)(u)=c(u)$; it is called a toggle node for $c$ if
$\mathcal{M}(c)(u)\not=c(u)$. Note that in any case
$\mathcal{M}(\mathcal{M}(c))(u)=c(u)$. Denote by $N^{i}_{f}(u)$ (resp.
$N^{i}_{t}(u)$) the number of neighbors of $u$ with color $i$ that are fixed
(resp. toggle) nodes for $c$.

First, we provide a simple characterization of fixed and toggle nodes for
$\mathcal{MIN}$ and $\mathcal{MAJ}$.

######  Lemma 10.

Let $T$ be a tree and $c\in\mathcal{C}^{2}_{\mathcal{MIN}}(T)$. A node $u$ of
$T$ is a fixed node of $c$ if and only if

$\lvert\mskip 0.90001muN_{t}^{1-c(u)}(u)-N_{t}^{c(u)}(u)\mskip
0.90001mu\rvert\leq N_{f}^{1-c(u)}(u)-N_{f}^{c(u)}(u)$

and a toggle node of $c$ if and only if

$\lvert\mskip 0.90001muN_{f}^{c(u)}(u)-N_{f}^{1-c(u)}(u)\mskip
0.90001mu\rvert<N_{t}^{c(u)}(u)-N_{t}^{1-c(u)}(u).$

###### Proof.

Let $u$ be a fixed node of $c$, i.e., $\mathcal{MIN}(c)(u)=c(u)$. Then
$N_{t}^{c(u)}(u)+N_{f}^{c(u)}(u)\leq N_{t}^{1-c(u)}(u)+N_{f}^{1-c(u)}(u)$.
Since $\mathcal{M}(\mathcal{M}(c))(u)=c(u)$ we also have
$N_{t}^{1-c(u)}(u)+N_{f}^{c(u)}(u)\leq N_{t}^{c(u)}(u)+N_{f}^{1-c(u)}(u)$.
This yields $-(N_{f}^{1-c(u)}(u)-N_{f}^{c(u)}(u))\leq
N_{t}^{1-c(u)}(u)-N_{t}^{c(u)}(u)\leq N_{f}^{1-c(u)}(u)-N_{f}^{c(u)}(u)$ which
proves that the condition is necessary.

Next assume $\lvert\mskip 0.90001muN_{t}^{1-c(u)}(u)-N_{t}^{c(u)}(u)\mskip
0.90001mu\rvert\leq N_{f}^{1-c(u)}(u)-N_{f}^{c(u)}(u)$. Then
$N_{t}^{c(u)}(u)-N_{t}^{1-c(u)}(u)\leq N_{f}^{1-c(u)}(u)-N_{f}^{c(u)}(u)$ and
$N^{c(u)}(u)\leq N^{1-c(u)}(u)$. Hence, $\mathcal{M}(c)(u)=c(u)$. The
assumption also implies that $N_{t}^{1-c(u)}(u)-N_{t}^{c(u)}(u)\leq
N_{f}^{1-c(u)}(u)-N_{f}^{c(u)}(u)$ resp.
$N_{f}^{c(u)}(u)+N_{t}^{1-c(u)}(u)\leq N_{f}^{1-c(u)}(u)+N_{t}^{c(u)}(u)$.
This yields $\mathcal{M}(\mathcal{M}(c))(u)=c(u)$. Hence, the condition is
sufficient. The result for toggle nodes is proved similarly. ∎

The proof of the following lemma is similar to the proof of Lemma 10.

######  Lemma 11.

Let $T$ be a tree and $c\in\mathcal{C}^{2}_{\mathcal{MAJ}}(T)$. A node $u$ of
$T$ is a fixed node of $c$ if and only if

$\lvert\mskip 0.90001muN_{t}^{1-c(u)}(u)-N_{t}^{c(u)}(u)\mskip
0.90001mu\rvert\leq N_{f}^{c(u)}(u)-N_{f}^{1-c(u)}(u)$

and a toggle node of $c$ if and only if

$\lvert\mskip 0.90001muN_{f}^{c(u)}(u)-N_{f}^{1-c(u)}(u)\mskip
0.90001mu\rvert<N_{t}^{1-c(u)}(u)-N_{t}^{c(u)}(u).$

###  5.2 Pure 2-Cycles

If $c\in\mathcal{P}_{\mathcal{M}}(T)$ then each node of $T$ is a toggle node.
In Theorem 16 we give a characterization $\mathcal{P}_{\mathcal{M}}(T)$, it
allows to generate all pure 2-cycles and compute $\lvert\mskip
0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$.

######  Lemma 12.

Let $T$ be a tree, $c\in\mathcal{C}_{\mathcal{M}}(T)$. Then
$c\in\mathcal{P}_{\mathcal{MIN}}(T)$ (resp.
$c\in\mathcal{P}_{\mathcal{MAJ}}(T)$) if and only if
$N^{c(u)}(u)>N^{1-c(u)}(u)$ (resp. $N^{c(u)}(u)<N^{1-c(u)}(u)$) for each node
$u$.

###### Proof.

We present the proof for $\mathcal{M}=\mathcal{MIN}$. If
$N^{c(u)}(u)>N^{1-c(u)}(u)$ for all nodes $u$ then all nodes are toggle nodes.
Hence, $N^{\mathcal{MIN}(c)(u)}(u)=N^{1-c(u)}(u)$. Thus,
$N^{1-\mathcal{MIN}(c)(u)}(u)>N^{\mathcal{MIN}(c)(u)}(u)$, i.e.,
$\mathcal{MIN}(\mathcal{MIN}(c))=c$, thus
$c\in\mathcal{C}^{2}_{\mathcal{MIN}}(T)$. Since no nodes are fixed nodes we
have $c\in\mathcal{P}_{\mathcal{MIN}}(T)$. The opposite statement follows from
Lemma 10. ∎

As in Sec. 4.1 we use properties of monochromatic edges to characterize pure
2-cycles. Corollary 14 is similar to Lemma 1 and is used to define the set
$E_{pure}(T)$.

######  Lemma 13.

Let $T$ be a tree, $c\in\mathcal{P}_{\mathcal{M}}(T)$, and $e=(u,w)\in E$ with
$c(u)\not=c(w)$ if $\mathcal{M}=\mathcal{MIN}$ and $c(u)=c(w)$ if
$\mathcal{M}=\mathcal{MAJ}$. Let $T_{u}$ (resp. $T_{w}$) be the subtree of
$T\setminus e$ that contains $u$ (resp. $w$). Then $u$ and $w$ have degree at
least 3, $T_{u}$ and $T_{w}$ contain at least 3 nodes, and $c$ induces a pure
2-cycle on both subtrees.

###### Proof.

We state the proof for $\mathcal{{M}}=\mathcal{{MIN}}$. Since $c$ is pure we
have $N^{c(u)}_{T}(u)>N^{1-c(u)}_{T}(u)$ and since $c(u)\not=c(w)$ we also
have $N^{1-c(u)}_{T}(u)\geq 1$. Hence,
$deg(u)=N^{c(u)}_{T}(u)+N^{1-c(u)}_{T}(u)\geq 3$. Similarly $deg(w)\geq 3$.
Let $v\in T_{u}$. If $v\not=u$ then all neighbors of $v$ in $T$ are in $T_{u}$
and thus $\lvert\mskip 0.90001muN^{c(u)}_{T_{u}}(u)\mskip
0.90001mu\rvert>\lvert\mskip 0.90001muN^{1-c(u)}_{T_{u}}(u)\mskip
0.90001mu\rvert$. Next consider the case $v=u$. Since $c$ is pure, there
exists in $N(u)$ at least one more node with color $c(u)$ than with color
$c(w)$. Thus, $u$ has at least two neighbors in $T_{u}$, hence $T_{u}$
contains at least three nodes. Since $\lvert\mskip
0.90001muN^{c(u)}_{T_{u}}(u)\mskip 0.90001mu\rvert=\lvert\mskip
0.90001muN^{c(u)}_{T}(u)\mskip 0.90001mu\rvert>\lvert\mskip
0.90001muN^{1-c(u)}_{T}(u)\mskip 0.90001mu\rvert=\lvert\mskip
0.90001muN^{1-c(u)}_{T_{u}}(u)\mskip 0.90001mu\rvert+1$ we have $\lvert\mskip
0.90001muN^{c(u)}_{T_{u}}\mskip 0.90001mu\rvert>\lvert\mskip
0.90001muN^{1-c(u)}_{T_{u}}(u)\mskip 0.90001mu\rvert$. Hence, Lemma 12 implies
that $c$ induces a pure 2-cycle for $\mathcal{{MIN}}$ on $T_{u}$. The same is
true for $T_{w}$. ∎

######  Corollary 14.

Let $T$ be a tree. If $c\in\mathcal{P}_{\mathcal{MIN}}(T)$, $F_{c}=\\{(u,w)\in
E\;|\;c(u)\not=c(w)\\}$, and $\hat{T}\in{\cal C}_{T}(F_{c})$ then
$\lvert\mskip 0.90001mu\hat{T}\mskip 0.90001mu\rvert\geq 3$ and $c$ induces a
monochromatic coloring on $\hat{T}$. If $c\in\mathcal{P}_{\mathcal{MAJ}}(T)$,
$F_{c}=\\{(u,w)\in E\;|\;c(u)=c(w)\\}$, and $\hat{T}\in{\cal C}_{T}(F_{c})$
then $\lvert\mskip 0.90001mu\hat{T}\mskip 0.90001mu\rvert\geq 3$ and $c$
induces an independent coloring on $\hat{T}$. Furthermore,
$(F_{c})_{v}<deg_{T}(v)/2$ for $v\in V$.

###### Proof.

Assume $\mathcal{{M}}=\mathcal{{MIN}}$. If $\hat{T}\in{\cal C}_{T}(F_{c})$
then $c(u)=c(w)$ for all $u,w\in\hat{T}$. Thus, by Lemma 13, $c$ induces a
monochromatic coloring on $\hat{T}$. Similarly, $c(u)\not=c(w)$ for all
$u,w\in\hat{T}$ for $\mathcal{{M}}=\mathcal{{MAJ}}$. Again Lemma 13, $c$
induces an independent coloring on $\hat{T}$. $\lvert\mskip
0.90001muN^{c(v)}(v)\mskip 0.90001mu\rvert>\lvert\mskip
0.90001muN^{1-c(v)}(v)\mskip 0.90001mu\rvert=(F_{c})_{v}$ since $c$ is pure.
Hence, $deg_{T}(v)>2(F_{c})_{v}$. ∎

Corollary 14 motivates the following definition of $E_{pure}(T)$. Note that
$E_{pure}(T)$ satisfies the hereditary property and $E_{pure}(T)=E_{fix}(T)$
if all degrees of $T$ are odd.

######  Definition 15.

Let $T$ be a tree. $E^{3}(T)$ denotes the set of all edges of $T$ where each
end node has degree at least three. $F\subseteq E^{3}(T)$ is called legal if
$F_{v}<deg(v)/2$ for each node $v$. $E_{pure}(T)$ denotes the set of all legal
subsets of $E^{3}(T)$.

######  Theorem 16.

For any tree $T$ there exists a bijection $\mathcal{B}_{pure}$ between
$E_{pure}(T)$ and $\mathcal{P}_{\mathcal{M}}(T)^{+}$.

###### Proof.

Let $F\in E_{pure}(T)$. We uniquely partition the nodes of $\mathcal{T}_{F}$
into two independent subsets $\mathcal{I}_{0}$ and $\mathcal{I}_{1}$ with
$v^{\ast}\in\mathcal{I}_{0}$. Assume $\mathcal{{M}}=\mathcal{{MIN}}$. Define a
mapping $C_{F}:{\cal C}_{T}(F)\rightarrow\\{0,1\\}$ by setting
$C_{F}(\hat{T})=i$ if $\hat{T}\in\mathcal{I}_{i}$. Based on $C_{F}$ we define
a coloring $c_{F}$ of $T$ as follows $c_{F}(v)=C_{F}(\hat{T})\text{ if
}v\in\hat{T}$. Note that $c_{F}(v^{\ast})=0$. $F$ uniquely defines $c_{F}$,
since for each node $v$ there is a unique $\hat{T}\in{\cal C}_{T}(F)$ that
contains $v$. First, we prove that
${c}_{F}\in\mathcal{P}_{\mathcal{MIN}}(T)^{+}$. For $v\in V$ let
$\hat{T}\in{\cal C}_{T}(F)$ with $v\in\hat{T}$. Then
$N(v)\cap\hat{T}=N_{T}^{c_{F}(v)}(v)$. Since $F\in E_{pure}(T)$ we have
$\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip 0.90001mu\rvert>deg(v)/2$.
Thus, $2\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip
0.90001mu\rvert>\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip
0.90001mu\rvert+\lvert\mskip 0.90001muN_{T}^{1-c_{F}(v)}(v)\mskip
0.90001mu\rvert$ and hence, $\lvert\mskip 0.90001muN_{T}^{c_{F}(v)}(v)\mskip
0.90001mu\rvert>\lvert\mskip 0.90001muN_{T}^{1-c_{F}(v)}(v)\mskip
0.90001mu\rvert$ for all $v$. Hence,
$c_{F}\in\mathcal{P}_{\mathcal{MIN}}(T)^{+}$ by Lemma 12. Now we can define
$\mathcal{B}_{pure}(F)={c}_{F}\text{ for each }F\in E_{pure}(T)$. Let
$F_{1}\not=F_{2}\in E_{pure}(T)$ and $e=(u,w)\in F_{1}\setminus F_{2}$. Then
$c_{F_{1}}(w)\not=c_{F_{1}}(u)$ and $c_{F_{2}}(w)=c_{F_{2}}(u)$. Hence,
$c_{F_{1}}\not=c_{F_{2}}$, i.e., $\mathcal{B}_{pure}(F)$ is injective.

Next, we prove that $\mathcal{B}_{pure}$ is surjective, i.e., for every
$c\in\mathcal{P}_{\mathcal{MIN}}(T)^{+}$ there exists $F_{c}\in E_{pure}(T)$
with $\mathcal{B}_{pure}(F_{c})=c$. For
$c\in\mathcal{P}_{\mathcal{MIN}}(T)^{+}$ define $F_{c}=\\{(u,w)\in
E\;|\;c(u)\not=c(w)\\}$. By Lemma 13 we have $F_{c}\in E^{3}(T)$. Let $v\in
V$. Since $c$ is a pure 2-cycle we have $\lvert\mskip
0.90001muN_{T}^{c(v)}(v)\mskip 0.90001mu\rvert>\lvert\mskip
0.90001muN_{T}^{1-c(v)}(v)\mskip 0.90001mu\rvert$, i.e., $deg(v)>2\lvert\mskip
0.90001muN_{T}^{1-c(v)}(v)\mskip 0.90001mu\rvert$. Since,
$(F_{c})_{v}=\lvert\mskip 0.90001muN_{T}^{1-c(v)}(v)\mskip 0.90001mu\rvert$ we
have $deg(v)/2>(F_{c})_{v}$. This yields $F_{c}\in E_{pure}(T)$. By the first
part of this proof we have
$\mathcal{B}_{pure}(F_{c})\in\mathcal{P}_{\mathcal{MIN}}(T)^{+}$. By Corollary
14 $\mathcal{B}_{pure}(F_{c})$ is for each tree $\hat{T}\in{\cal
C}_{T}(F_{c})$ a monochromatic coloring with
$\mathcal{B}_{pure}(F_{c})(v)=c(v)$ for all $v\in\hat{T}$. Hence, $c$ and
$\mathcal{B}_{pure}(F_{c})$ define the same coloring of $T$, i.e.,
$\mathcal{B}_{pure}(F_{c})=c$.

The proof for the case $\mathcal{{M}}=\mathcal{{MAJ}}$ is similar. The main
differences are that we define $c_{F}$ such that it induces an independent
coloring on each $\hat{T}\in{\cal C}_{T}(F)$ and in the second part we define
$F_{c}=\\{(u,w)\in E\;|\;c(u)=c(w)\\}$. ∎

######  Corollary 17.

Every tree $T$ has a pure coloring for the minority and the majority process.
$T$ has a non-monochromatic (resp. non-independent) pure coloring for the
minority (resp. majority) process if and only if there exist an edge $(u,w)\in
T$ such that $deg(u)\geq 3$ and $deg(w)\geq 3$.

###### Proof.

We provide the proof for $\mathcal{M}=\mathcal{MIN}$. The result follows from
Theorem 16. Since $\emptyset\in E_{pure}(T)$ we have
$c_{\emptyset}\in\mathcal{F}_{\mathcal{M}}(T)^{+}$. $c_{\emptyset}$ is a
monochromatic coloring. $T$ has a non-monochromatic pure coloring if and only
if $E_{pure}(T)\not=\emptyset$. This is equivalent to having an edge with the
stated properties. ∎

######  Corollary 18.

Let $P$ be a path and $c\in\mathcal{C}(P)$. Then
$c\in\mathcal{P}_{\mathcal{MIN}}(P)$ (resp.
$c\in\mathcal{P}_{\mathcal{MAJ}}(P)$) if and only if $c(v)=c(w)$ (resp.
$c(v)\not=c(w)$) for each edge $(v,w)$ of $P$.

###### Proof.

Clearly $E_{pure}=\emptyset$. Hence,
$\mathcal{P}_{\mathcal{M}}(P)^{+}=\\{c_{\emptyset}\\}$ by Theorem 16. Hence,
$c$ is monochromatic (resp. independent) for $\mathcal{M}=\mathcal{MIN}$
(resp. $\mathcal{M}=\mathcal{MAJ}$). ∎

Since $E_{pure}(T)\subseteq E_{fix}(T)$ we have
$\mathcal{P}_{\mathcal{MAJ}}(T)\subseteq\mathcal{F}_{\mathcal{MIN}}(T)$ and
$\mathcal{P}_{\mathcal{MIN}}(T)\subseteq\mathcal{F}_{\mathcal{MAJ}}(T)$. Fig.
3 shows that there are trees $T$ where
$\mathcal{P}_{\mathcal{MAJ}}(T)\subset\mathcal{F}_{\mathcal{MIN}}(T)$ and
$\mathcal{P}_{\mathcal{MIN}}(T)\subset\mathcal{F}_{\mathcal{MAJ}}(T)$.

Figure 3: The left coloring is in
$\mathcal{F}_{\mathcal{MAJ}}(T)\setminus\mathcal{P}_{\mathcal{MIN}}(T)$, the
right one is in
$\mathcal{F}_{\mathcal{MIN}}(T)\setminus\mathcal{P}_{\mathcal{MAJ}}(T)$.

###  5.3 Counting Pure 2-Cycles

Theorem 16 allows to determine the pure 2-cycles of a tree $T$, and thus,
$\lvert\mskip 0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$.
Since $E_{pure}(T)\subseteq E_{fix}(T)$ we have $\lvert\mskip
0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert\leq\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$ and $\lvert\mskip
0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert\leq
2F_{n-\lceil\Delta/2\rceil}$ by Theorem 8. To generate all pure 2-cycles
Algorithm 1 can be adopted, note that $E_{pure}(T)$ has the hereditary
property. The difference is that it uses $E^{3}(T)$ and the corresponding
notion of legal. The algorithm works in time $O(n+\lvert\mskip
0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert\lvert\mskip
0.90001muE^{3}(T)\mskip 0.90001mu\rvert)$. Next we provide a better upper
bound for $\lvert\mskip 0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip
0.90001mu\rvert$. Let $e_{T}=\lvert\mskip 0.90001muE^{3}(T)\mskip
0.90001mu\rvert$.

######  Lemma 19.

Let $T$ be a tree, then $e_{T}\leq(n-4)/2$.

###### Proof.

The proof is by induction on $n$. If $n<6$ then $e_{T}=0$ and for $n=6$ we
have $e_{T}\leq 1$. So let $n>6$. Let $v$ be a node with $deg(v)=2$. Let
$T^{\prime}$ be the tree that is constructed from $T$ by removing node $v$ and
connecting the two neighbors of $v$ by an edge. Then $e_{T}=e_{T^{\prime}}$.
By induction $e_{T^{\prime}}\leq(n-5)/2<(n-4)/2$. Hence we can assume that
$deg(v)\not=2$ for all nodes $v$ of $T$. Let $v$ be a node with $deg(v)\geq
4$. Then by induction, no neighbor of a $v$ is a leaf. Hence, each neighbor of
$v$ has degree at least $3$. Let $w$ be a neighbor of $v$ and $(v,w)$ an edge.
Let $T_{1}$ be the connected component of $T\setminus e$ that contains $v$ and
$T_{2}$ the other component with the additionally edge $e$. Let $T_{i}$ have
$n_{i}$ nodes. Then $n_{1}+n_{2}=n+1$ and $e_{T}=1+e_{T_{1}}+e_{T_{2}}$. By
induction $e_{T_{i}}\leq(n_{i}-4)/2$. Thus,

$e_{T}\leq 1+(n_{1}-4)/2+(n_{2}-4)/2=(n_{1}+n_{2}-6)/2=(n-5)/2<(n-4)/2.$

It remains the case each node has either degree $1$ or $3$. Let $l$ be the
number of leaves of $T$, then there are $n-l$ nodes of degree $3$. Then
$e_{T}=n-l-1$ (remove all leaves, then $e_{T}$ edges remain). We have
$l+3(e_{T}+1)=2(n-1)$ and $l+e_{T}+1=n$. Thus $n-1-e_{T}+3(e_{T}+1)=2(n-1)$.
This yields $2e_{T}=n-4$ which completes the proof. ∎

The last lemma implies $\lvert\mskip
0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert\leq
2^{1+(n-4)/2}$. This bound is purely based on the bound for $\lvert\mskip
0.90001muE^{3}(T)\mskip 0.90001mu\rvert$. By utilizing the constraints imposed
by $E_{pure}(T)$ better bounds may be derived. The tree $H_{n}$ with $n\equiv
0(2)$ that consists of a path of length $(n+2)/2$ and a single node attached
to each inner node of the path (see Fig. 4) shows that the bound of Lemma 19
is sharp, but there is large gap between $\lvert\mskip
0.90001muE^{3}(H_{n})\mskip 0.90001mu\rvert$ and $\lvert\mskip
0.90001muE_{pure}(H_{n})\mskip 0.90001mu\rvert$.

Figure 4: The graph $H_{10}$, the three edges belonging to $E^{3}(H_{10})$ are
depicted by solid lines. In general we have $\lvert\mskip
0.90001muE^{3}(H_{n})\mskip 0.90001mu\rvert=2^{(n-4)/2}$ and $\lvert\mskip
0.90001muE_{pure}(H_{n})\mskip 0.90001mu\rvert=F_{n/2}$.

###  5.4 Block Trees of 2-Cycles

In this section we consider general 2-cycles, i.e., those that have both fixed
and toggle nodes. We characterize the coarse grain structure of
$\mathcal{C}^{2}_{\mathcal{M}}(T)$, called the block tree of $T$.

######  Definition 20.

Let $T$ be a tree and $c\in{\cal C}^{2}_{\mathcal{M}}(T)$. Let $V_{f}$ (resp.
$V_{t}$) be the set of fixed (resp. toggle) nodes of $c$ and $T^{f}$ (resp.
$T^{t}$) the subgraph of $T$ induced by $V_{f}$ (resp. $V_{t}$).

The next result shows that a 2-cycle $c$ induces a structure on $T$ that
allows to define a hyper-tree $\mathcal{B}_{c}(T)$.

######  Lemma 21.

Let $T$ be a tree, $c\in{\cal C}^{2}_{\mathcal{M}}(T)$, and $T^{\prime}$ a
connected component of $T^{f}$ (resp. $T^{t}$). Then $c$ induces a fixed point
(resp. a pure 2-cycle) on $T^{\prime}$.

###### Proof.

We present the proof for $\mathcal{MIN}$. Let $T^{\prime}$ be a connected
component of $T^{f}$ and $u$ a node of $T^{\prime}$. With respect to $T$ we
have $\lvert\mskip 0.90001muN_{t}^{1-c(u)}(u)-N_{t}^{(u)}(u)\mskip
0.90001mu\rvert\leq N_{f}^{1-c(u)}(u)-N_{f}^{c(u)}(u)$ by Lemma 10.
Restricting $c$ to $T^{\prime}$ gives
$N_{T^{\prime}}^{c(u)}(u)=N_{f}^{c(u)}(u)$ and
$N_{T^{\prime}}^{1-c(u)}(u)=N_{f}^{1-c(u)}(u)$. This yields
$N_{T^{\prime}}^{1-c(u)}(u)\geq N_{T^{\prime}}^{c(u)}(u)$. This proves that
$u$ is a fixed node of $T^{\prime}$ for $c$. Hence, $c$ is a fixed point for
$T^{\prime}$. The result about components of $T^{t}$ is proved similarly. The
result for $\mathcal{MAJ}$ is based on Lemma 11. ∎

Lemma 21 provides the base to define the block tree of a coloring $c\in{\cal
C}^{2}_{\mathcal{M}}(T)$.

######  Definition 22.

Let $T$ be a tree, $c\in{\cal C}^{2}_{\mathcal{M}}(T)$, and
$T_{1},\ldots,T_{s}$ the connected components of $T^{f}$ and $T^{t}$. The
block tree $\mathcal{B}_{c}(T)$ of $T$ for $c$ is a tree with nodes
$\\{T_{1},\ldots,T_{s}\\}$, nodes $T_{i}$ and $T_{j}$ are connected if there
exists $(u,w)\in E$ with $u\in T_{i}$ and $w\in T_{j}$. A node $T_{i}$ is
called a fixed block (resp. toggle block) of $\mathcal{B}_{c}(T)$ if $T_{i}$
is a connected component of $T^{f}$ (resp. $T^{t}$).

Obviously $\mathcal{B}_{c}(T)$ is a tree. $\mathcal{B}_{c}(T)$ is uniquely
defined, but different 2-cycles can induce the same block tree (see Fig. 5).
Each edge $e$ of $\mathcal{B}_{c}(T)$ connects a fixed block with a toggle
block, $e$ uniquely corresponds to an edge of $T$. For convenience we denote
this edge also by $e$. If $T_{i}$ is a toggle block then obviously
$\lvert\mskip 0.90001muT_{i}\mskip 0.90001mu\rvert\geq 2$, since all
neighboring blocks are fixed blocks. Fixed blocks can consist of a single node
only (see Fig. 6).

The goal of this section is to present a characterization of the set of all
block trees for a given tree $T$ similar to Theorem 16, i.e., the trees
$T_{B}$ for which there exists $c\in{\cal C}^{2}_{\mathcal{M}}(T)$ such that
$T_{B}=\mathcal{B}_{c}(T)$. The following theorem summarizes properties of
2-cycles.

######  Theorem 23.

Let $T$ be a tree, $c\in\mathcal{C}^{2}_{\mathcal{M}}(T)$, and $e=(u,w)$ an
edge of $\mathcal{B}_{c}(T)$. Then

  1. 1.

If $deg_{T}(u)=2$ then $u$ is a fixed node.

  2. 2.

$\min(deg_{T}(u),deg_{T}(w))\geq 2$ and $\max(deg_{T}(u),deg_{T}(w))\geq 3$.

  3. 3.

If $T_{0}$ is a node of $\mathcal{B}_{c}(T)$, $v\in T_{0}$, $deg_{T_{0}}(v)=1$
and $deg_{T}(v)\equiv 0(2)$ then $v$ is a fixed node and $T_{0}$ is a fixed
block.

  4. 4.

If $T_{0}=\\{v\\}$ is a node of $\mathcal{B}_{c}(T)$ then $v$ is a fixed node,
$T_{0}$ is a fixed block, and $deg_{T}(v)$ is even.

###### Proof.

Assume $\mathcal{M}=\mathcal{MIN}$, the proof for $\mathcal{MAJ}$ is similar
and uses Lemma 11. Assume that $u$ is toggle node. Then $\lvert\mskip
0.90001muN^{c(u)}(u)\mskip 0.90001mu\rvert>\lvert\mskip
0.90001muN^{1-c(u)}\mskip 0.90001mu\rvert$. Thus, if $\lvert\mskip
0.90001muN^{1-c(u)}\mskip 0.90001mu\rvert>0$ then $deg_{T}(u)\geq 3$.
Therefore, $\lvert\mskip 0.90001muN^{1-c(u)}\mskip 0.90001mu\rvert=0$ and
$\lvert\mskip 0.90001muN^{c(u)}(u)\mskip 0.90001mu\rvert=2$. Since $u$ is
toggle node, both neighbors must change their color, i.e., both are toggle
nodes. This yields that $w$ is a toggle node. Contradiction, since $e(u,w)$ is
an edge of $\mathcal{B}_{c}(T)$.

WLOG we assume that $u$ is a fixed node while $w$ toggles its color. Assume
that $\min(deg(u),deg(w))=1$. If $deg(u)=1$ then $u$ cannot be a fixed node
because $w$ toggles its color. Similarly, $w$ cannot have degree $1$. Hence,
$\min(deg(u),deg(w))\geq 2$. Assume that $deg(u)=deg(w)=2$. Then by the first
part, both nodes are fixed nodes. Contradiction. Assume that $v$ is a toggle
node. Then $N_{t}^{c(v)}=1$ and $N_{t}^{1-c(v)}=0$. Hence, by Lemma 10 we have
$N_{f}^{1-c(v)}=N_{f}^{c(v)}$ thus, $deg_{T}(v)=1+2N_{f}^{c(v)}\equiv 1(2)$.
Contradiction. Let $T_{0}=\\{v\\}$. If $v$ is a toggle node then all neighbors
are fixed nodes. Hence, $v$ is also a fixed node. Contradiction. Lemma 10
yields that $deg_{T}(v)$ is even. ∎

Figure 5: Two colorings leading to the same block tree. For the minority
process both colorings define the same block tree. The left block node is a
toggle node while the right is a fixed point.

Figure 6: A block tree consisting of two toggle blocks and one fixed block
with a single node.

The last theorem list properties of $\mathcal{B}_{c}(T)$ for
$c\in\mathcal{C}^{2}_{\mathcal{M}}(T)$. As before we take these properties to
identify a set of edges $F_{c}$ such that
${\mathcal{T}}_{F_{c}}=\mathcal{B}_{c}(T)$. The following two definitions
provide a formal framework for this purpose.

######  Definition 24.

Let $T$ be a tree. $E^{\,2.5}(T)$ denotes the set of edges of $T$, where one
end node has degree at least two and the other has degree at least $3$. For
$F\subseteq E^{\,2.5}(T)$ a component $\hat{T}\in{\cal C}_{T}(F)$ is called
fixed if $\lvert\mskip 0.90001mu\hat{T}\mskip 0.90001mu\rvert=1$ or if there
exists $v\in\hat{T}$ such that $deg_{T}(v)\equiv 0(2)$ and
$deg_{\hat{T}}(v)=1$. $Fix(T,F)$ denotes the set of all fixed components of
${\cal C}_{T}(F)$.

######  Definition 25.

Let $T$ be a tree. $F\subseteq E^{\,2.5}(T)$ is called legal if all components
of $Fix(T,F)$ are fully contained in $\mathcal{I}_{0}(\mathcal{T}_{F})$ and if
$T_{0}\in{\cal C}_{T}(F)$ with $T_{0}=\\{v\\}$ then $deg_{T}(v)\equiv 0(2)$.
$E_{block}(T)$ denotes the set of all legal subsets of $E^{\,2.5}(T)$.

The next result reveals the significance of $E_{block}(T)$ for block trees.

######  Lemma 26.

Let $T$ be a tree, $c\in\mathcal{C}^{2}_{\mathcal{M}}(T)$, and $F_{c}$ the
edges of $\mathcal{B}_{c}(T)$. Then ${F_{c}}\in E_{block}(T)$.

###### Proof.

Note that $\mathcal{T}_{F_{c}}=\mathcal{B}_{c}(T)$. By Theorem 23.2 we have
$F_{c}\subseteq E^{\,2.5}(T)$. By construction of $\mathcal{B}_{c}(T)$ and
Theorem 23.4 and 23.3 we have
$Fix(T,F_{c})\subseteq\mathcal{I}_{0}(\mathcal{T}_{F_{c}})$. Theorem 23.4
completes the proof. ∎

######  Definition 27.

Let $T$ be a tree. A coloring $c\in{\cal C}^{2}_{\mathcal{MIN}}(T)$ is called
canonical if $c$ induces a monochromatic (resp. independent) coloring on each
connected component of $T^{t}$ (resp. $T^{f}$). A coloring $c\in{\cal
C}^{2}_{\mathcal{MAJ}}(T)$ is called canonical if $c$ induces an independent
(resp. monochromatic) coloring on each connected component of $T^{t}$ (resp.
$T^{f}$).

The next result lays the groundwork for our characterization of block trees.

######  Lemma 28.

Let $T$ be a tree and $F\in E_{block}(T)$. There exits
$c\in\mathcal{C}^{2}_{\mathcal{M}}(T)$ with
$\mathcal{B}_{c}(T)=\mathcal{T}_{F}$ such that $c$ is canonical and
$\mathcal{I}_{0}$ (resp. $\mathcal{I}_{1}$) is the set of fixed (resp. toggle)
nodes of $c$.

###### Proof.

Assume $\mathcal{M}=\mathcal{MIN}$, $\mathcal{M}=\mathcal{MAJ}$ is similar and
uses Lemma 11. The proof is by induction on $\lvert\mskip 0.90001muF\mskip
0.90001mu\rvert$. The case $\lvert\mskip 0.90001muF\mskip 0.90001mu\rvert=0$
is obvious, $c$ is the monochromatic coloring. Let $\lvert\mskip
0.90001muF\mskip 0.90001mu\rvert>0$. Let $L\in\mathcal{T}_{F}$ be a leaf and
$e=(u,w)\in F$ such that $w\in L$. Then $\lvert\mskip 0.90001muL\mskip
0.90001mu\rvert\geq 2$ if $L\in\mathcal{I}_{0}(\mathcal{T}_{F})$ and
$\lvert\mskip 0.90001muL\mskip 0.90001mu\rvert\geq 3$ if
$L\in\mathcal{I}_{1}(\mathcal{T}_{F})$. Remember that
$\mathcal{I}_{0}(\mathcal{T}_{F})$ contains the fixed components of
$\mathcal{T}_{F}$. By the definition of $E_{block}(T)$ we have to consider
four cases.

Case 1: $L\in\mathcal{I}_{0}(\mathcal{T}_{F})$ and $\lvert\mskip
0.90001muL\mskip 0.90001mu\rvert>2$. We construct a tree $\tilde{T}$ as
follows: Remove from $T$ all nodes of $L$ except $w$ and add a new neighbor
$v$ to $w$. Then $\lvert\mskip 0.90001mu\tilde{T}\mskip
0.90001mu\rvert<\lvert\mskip 0.90001muT\mskip 0.90001mu\rvert$. Then
$deg_{T}(u)>2$ otherwise $L$ would not be in
$\mathcal{I}_{0}(\mathcal{T}_{F})$. Hence, $F\subseteq E^{2.5}(\tilde{T})$.
Denote the leaf of ${\cal C}_{\tilde{T}}(F)$ consisting of $v$ and $w$ by
$\tilde{L}$. Thus, $\tilde{L}\in Fix(\tilde{T},F)$ and
$Fix(\tilde{T},F)=Fix(T,F)\cup\tilde{L}\setminus
L\subseteq\mathcal{I}_{0}(\mathcal{T}_{F})$. Let $T_{0}=\\{v\\}\in{\cal
C}_{\tilde{T}}(F)$. Then, $T_{0}\in{\cal C}_{{T}}(F)$. Hence,
$deg_{T}(v)\equiv 0(2)$ by assumption. Since
$T_{0}\in\mathcal{I}_{0}(\mathcal{T}_{F})$ we also have
$deg_{\tilde{T}}(v)\equiv 0(2)$. This shows that $\tilde{T}$ and $F$ satisfy
the theorem’s assumption. Hence, by induction there exists a canonical
coloring $\tilde{c}\in{\cal C}^{2}(\tilde{T})$ with
$\mathcal{B}_{\tilde{c}}(\tilde{T})=\mathcal{T}_{F}$ satisfying all
properties. We can extend $\tilde{c}$ to a coloring $c\in{\cal C}^{2}({T})$ by
setting $c(x)=\tilde{c}(x)$ for all nodes $x\in T\setminus L$,
$c(w)=\tilde{c}(w)$, and color the remaining nodes of $L$ in the canonical way
for a fixed point.

Case 2: $L\in\mathcal{I}_{0}(\mathcal{T}_{F})$ and $\lvert\mskip
0.90001muL\mskip 0.90001mu\rvert=2$. Let $\tilde{F}=F\setminus e$. Let $v\in
L$ be a neighbor of $w$ and set $\tilde{T}=T\setminus v$. Let $T_{u}\in{\cal
C}_{{T}}({F})$ with $u\in T_{u}$. Then
$T_{u}\in\mathcal{I}_{1}(\mathcal{T}_{F})$ and thus, $\lvert\mskip
0.90001muT_{u}\mskip 0.90001mu\rvert>1$, $deg_{T_{u}}(u)\geq 1$ and
$deg_{T}(u)\geq 3$. Let $\tilde{T}_{u}\in{\cal C}_{\tilde{T}}(\tilde{F})$ with
$u\in\tilde{T}_{u}$. Then $w\in\tilde{T}_{u}$,
$\tilde{T}_{u}\in\mathcal{I}_{1}(\mathcal{T}_{F})$ and
$T_{u}\subset\tilde{T}_{u}$. Clearly, $\tilde{F}\subseteq E^{2.5}(\tilde{T})$.
Let $T_{0}=\\{v_{0}\\}\in{\cal C}_{\tilde{T}}(\tilde{F})$ with $\lvert\mskip
0.90001muT_{0}\mskip 0.90001mu\rvert=1$. Then $T_{0}\in{\cal C}_{{T}}({F})$,
thus $deg_{T}(v_{0})\equiv 0(2)$. Hence, $deg_{\tilde{T}}(v_{0})\equiv 0(2)$.
Let $\hat{T}\in{\cal C}_{\tilde{T}}(\tilde{F})$ and $v_{0}\in\hat{T}$ with
$deg_{\hat{T}}(v_{0})=1$, $deg_{\tilde{T}}(v_{0})\equiv 0(2)$. Assume
$\hat{T}=\tilde{T}_{u}$. Then $v_{0}\not=w$ since
$deg_{\tilde{T}}(w)=1\not\equiv 0(2)$. Thus, $\hat{T}=\tilde{T}_{u}$ if
$v_{0}\in\hat{T}$ with $deg_{\hat{T}}(v_{0})=1$ for some $v_{0}\not=w$. Hence,
$\hat{T}\in
Fix(\tilde{T},\tilde{F})=Fix(T,F)\subseteq\mathcal{I}_{0}(\mathcal{T}_{F})=\mathcal{I}_{0}(\mathcal{\tilde{T}}_{\tilde{F}})$.

Therefore, $\tilde{T}$ and $\tilde{F}$ satisfy the theorem’s assumption. By
induction there exists a canonical coloring $\tilde{c}\in{\cal
C}^{2}(\tilde{T})$ with
$\mathcal{B}_{\tilde{c}}(\tilde{T})=\mathcal{T}_{\tilde{F}}$ satisfying all
properties. Since $\tilde{T}_{u}\in\mathcal{I}_{1}(T)$ all nodes of
$\tilde{T}_{u}$ have the same color, thus $N_{t}^{1-\tilde{c}(u)}(u)=0$ and
$\tilde{c}(u)=\tilde{c}(w)$. By Lemma 10 we have $\lvert\mskip
0.90001muN_{f}^{\tilde{c}(u)}(u)-N_{f}^{1-\tilde{c}(u)}(u)\mskip
0.90001mu\rvert<N_{t}^{\tilde{c}(u)}(u)$. We change $\tilde{c}$ to a coloring
$c$ of $T$ as follows. First, we set $c(x)=\tilde{c}(x)$ for all
$x\not\in\\{w,v\\}$. We apply Lemma 10 to prove that $u$ is still a toggle
node for $c$.

If $N_{f}^{\tilde{c}(u)}(u)>N_{f}^{1-\tilde{c}(u)}(u)$ we set
$c(w)=1-\tilde{c}(w)$ and $c(v)=\tilde{c}(w)$. If
$N_{f}^{\tilde{c}(u)}(u)<N_{f}^{1-\tilde{c}(u)}(u)$ we set $c(w)=\tilde{c}(w)$
and $c(v)=1-\tilde{c}(w)$. At last consider the case
$N_{f}^{\tilde{c}(u)}(u)=N_{f}^{1-\tilde{c}(u)}(u)$. If
$N_{t}^{\tilde{c}(u)}(u)=2$ then $N_{t}^{{c}(u)}(u)=1$, i.e.,
$deg_{{T_{u}}}(u)=1$. Also $deg_{\tilde{T}}(u)=2N_{f}^{\tilde{c}(u)}(u)+2$,
i.e, $deg_{{T}}(u)\equiv 0(2)$. Hence,
$T_{u}\in\mathcal{I}_{0}(\mathcal{T}_{F})$. Contradiction and thus
$N_{t}^{\tilde{c}(u)}(u)>2$. Set $c(w)=1-\tilde{c}(w)$ and
$c(v)=\tilde{c}(w)$. Then $N_{t}^{{c}(u)}(u)>1$ and thus, $\lvert\mskip
0.90001muN_{f}^{c(u)}-N_{f}^{1-c(u)}\mskip
0.90001mu\rvert=1<N_{t}^{{c}(u)}(u)$. Therefore, $c$ has the desired
properties.

Case 3: $L\in\mathcal{I}_{1}(T)$ and $\lvert\mskip 0.90001muL\mskip
0.90001mu\rvert>3$.
Construct a tree $\tilde{T}$ as follows: Remove from $T$ all nodes of $L$
except $w$ and add two new neighbors $v_{1},v_{2}$ to $w$. Then $\lvert\mskip
0.90001mu\tilde{T}\mskip 0.90001mu\rvert<\lvert\mskip 0.90001muT\mskip
0.90001mu\rvert$. Note that $deg_{T}(w)\geq 3$ otherwise
$L\in\mathcal{I}_{0}(\mathcal{T}_{F})$. Hence, $F\subseteq
E^{2.5}(\tilde{T})$. Denote the leaf of $\mathcal{I}_{\tilde{T}}(F)$
consisting of $v_{1},v_{2}$ and $w$ by $\tilde{L}$. Then
$\tilde{L}\in\mathcal{I}_{1}(T)$ and hence,
$Fix(\tilde{T},F)=Fix(T,F)\subseteq\mathcal{I}_{0}(\mathcal{T}_{F})$. Let
$T_{0}=\\{v\\}\in{\cal C}_{\tilde{T}}(F)$. Then, $T_{0}\in{\cal C}_{{T}}(F)$.
Hence, $deg_{T}(v)\equiv 0(2)$ by assumption. Then also
$deg_{\tilde{T}}(v)\equiv 0(2)$. This shows that $\tilde{T}$ and $F$ satisfy
the assumption of the theorem. Hence, by induction there exists a canonical
coloring $\tilde{c}\in{\cal C}^{2}(\tilde{T})$ with
$\mathcal{B}_{\tilde{c}}(\tilde{T})=\mathcal{T}_{F}$. We extend $\tilde{c}$ to
a coloring $c\in{\cal C}^{2}({T})$ by setting $c(x)=\tilde{c}(w)$ for all
$x\in L$ and $c(x)=\tilde{c}(x)$ for all other nodes $x$. Clearly $c$
satisfies the required conditions.

Case 4: $L\in\mathcal{I}_{1}(T)$ and $\lvert\mskip 0.90001muL\mskip
0.90001mu\rvert=3$.
Let $\tilde{F}=F\setminus e$. Since $L\in\mathcal{I}_{1}(T)$ we have
$deg_{L}(w)=2$. Let $v_{1},v_{2}$ be the neighbors of $w$ in $L$ and set
$\tilde{T}=T\setminus v_{1}$. Let $T_{u}\in{\cal C}_{{T}}({F})$ with $u\in
T_{u}$. Then $T_{u}\in\mathcal{I}_{0}(\mathcal{T}_{F})$. Let
$\tilde{T}_{u}\in{\cal C}_{\tilde{T}}(\tilde{F})$ with $u\in\tilde{T}_{u}$.
Then $\tilde{T}_{u}\in\mathcal{I}_{0}(\mathcal{T}_{F})$ and
$T_{u}\subseteq\tilde{T}_{u}$.

Clearly, $\tilde{F}\subseteq E^{2.5}(\tilde{T})$. Let
$T_{0}=\\{v_{0}\\}\in{\cal C}_{\tilde{T}}(\tilde{F})$ with $\lvert\mskip
0.90001muT_{0}\mskip 0.90001mu\rvert=1$. Then $T_{0}\in{\cal C}_{{T}}({F})$,
thus $deg_{T}(v_{0})\equiv 0(2)$. Hence, $deg_{\tilde{T}}(v_{0})\equiv 0(2)$.

Let $\hat{T}\in{\cal C}_{\tilde{T}}(\tilde{F})$ and $v_{0}\in\hat{T}$ with
$deg_{\hat{T}}(v_{0})=1$ and $deg_{\hat{T}}(v_{0})\equiv 0(2)$. If
$\hat{T}=\tilde{T}_{u}$ then $\hat{T}\in\mathcal{I}_{0}(\mathcal{T}_{F})$.
Otherwise $\hat{T}\in{\cal C}_{{T}}({F})$ and thus,
$\hat{T}\in\mathcal{I}_{0}(\mathcal{T}_{F})$. Therefore, $\tilde{T},\tilde{F}$
satisfy the assumption of the theorem. By induction there exists a canonical
coloring $\tilde{c}\in{\cal C}^{2}(\tilde{T})$ with
$\mathcal{B}_{\tilde{c}}(\tilde{T})=\mathcal{T}_{\tilde{F}}$. Since
$\tilde{T}_{u}\in\mathcal{I}_{0}(\tilde{T}_{\tilde{F}})$ neighboring nodes of
$\tilde{T}_{u}$ have different colors. Since
$\tilde{T}_{u}\in\mathcal{I}_{0}(\mathcal{T}_{F})$ neighboring nodes of
$\tilde{T}_{u}$ have different colors, thus $N_{f}^{c(u)}(u)=0$ and
$N_{f}^{1-c(u)}(u)>0$. By Lemma 10 we have $\lvert\mskip
0.90001muN_{t}^{1-c(u)}(u)-N_{t}^{c(u)}(u)\mskip
0.90001mu\rvert<N_{f}^{1-c(u)}(u)$. We change $\tilde{c}$ to a coloring $c$ of
$T$ as follows. First, we set $c(x)=\tilde{c}(x)$ for all
$x\not\in\\{w,v_{1},v_{2}\\}$. If $N_{t}^{1-c(u)}(u)>N_{t}^{c(u)}(u)$ we set
$c(w)=\tilde{c}(u)$. If $N_{t}^{1-c(u)}(u)<N_{t}^{c(u)}(u)$ we set
$c(w)=1-\tilde{c}(u)$. In both cases we set $c(v_{1})=c(v_{2})=c(w)$. At last
consider the case $N_{t}^{c(u)}(u)=N_{t}^{1-c(u)}(u)$. Since
$N_{f}^{1-c(u)}(u)>0$ we can take any of the two approaches. Clearly $c$ has
the desired properties. ∎

######  Theorem 29.

For a tree $T$ there exists a bijection $\mathcal{B}_{block}$ between
$E_{block}(T)$ and the set of block trees of $T$ of the minority and the
majority process.

###### Proof.

The existence of $\mathcal{B}_{block}$ follows from Lemma 26 and 28. ∎

The following result is an immediate implication of the last theorem.

######  Corollary 30.

Let $T$ be a tree where all nodes have odd degree. Then

$E_{block}(T)=\\{F\subseteq E^{3}(T)\;|\;{\cal C}_{T}(F)\text{ does not
contain a component of size }1\\}.$

If $P$ is a path then
$\mathcal{C}^{2}_{\mathcal{M}}(P)=\mathcal{P}_{\mathcal{M}}(P)$.

###  5.5 Counting Block Trees

The concept of Algorithm 1 can not be used to generate all elements of
$E_{block}(T)$ because $E_{block}(T)$ does not have the hereditary property
(see Fig. 7). Since $E_{block}(T)\subseteq E_{fix}(T)$ each upper bound for
$\lvert\mskip 0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$ is
also an upper bound for $\lvert\mskip
0.90001mu\mathcal{C}^{2}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$. A naive way
to generate all block trees of a tree is to iterate over the set $E_{fix}(T)$
and test, whether an element is legal according to Def. 25.

Figure 7: The left two drawings show a coloring from
$\mathcal{C}^{2}_{\mathcal{M}}(T)$ which corresponds to the set $F\in
E_{block}(T)$ which consists of three bold edges. The two fixed blocks are
highlighted. In the right most drawing the tree $\mathcal{T}_{F^{\prime}}$ for
the set $F^{\prime}\subset F$ of the two marked edges is shown. $F^{\prime}$
is not legal, because two neighboring components are fixed by Def. 24.

##  6 Conclusion and Open Problems

In this paper we provided characterizations of several categories of colorings
of trees for the minority and majority process in terms of subsets of the tree
edges. This means that the class of trees is the first nontrivial graph class
for which a complete characterization of fixed points for the
minority/majority process exists. This includes an algorithm to enumerate all
fixed points and upper bounds for the number of fixed points.

There are several open questions that are worth pursuing. Firstly, is it
possible to characterize fixed points and pure colorings for other graph
classes? Clearly, the results for trees do not hold for general graphs, e.g.
for cycles. But, it might be possible to use the same approach, i.e., find
suitable subsets of the edge set similar to $E_{fix}$.

Furthermore, the current work for trees can be improved. It would be
interesting to find better general upper bounds for $\lvert\mskip
0.90001mu\mathcal{F}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$ and $\lvert\mskip
0.90001mu\mathcal{P}_{\mathcal{M}}(T)\mskip 0.90001mu\rvert$ for trees. Also,
we believe that the run-time of Algorithm 1 can be improved. Moreover, an
algorithm to enumerate all block trees is an open problem. Finally, a full
characterization of all 2-cycles with the help of a subset of the power set of
the tree edges is still missing.

Another line of research is to consider random trees and compute the expected
number of fixed points and pure colorings. Using our results, it suffices to
compute the expected sizes of $\lvert\mskip 0.90001muE_{fix}(T)\mskip
0.90001mu\rvert$ and $\lvert\mskip 0.90001muE_{pure}(T)\mskip 0.90001mu\rvert$
for these trees.

## References

  * [1] Z. Agur.  Fixed points of majority rule cellular automata with application to plasticity and precision of the immune system.  Complex Systems, 5(3):351–357, 1991.
  * [2] Z. Agur, A. Fraenkel, and S. Klein.  The number of fixed points of the majority rule.  Discrete Mathematics, 70(3):295–302, 1988.
  * [3] T. Akutsu, S. Kuhara, O. Maruyama, and S. Miyano.  A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions.  Genome Informatics, 9:151–160, 1998.
  * [4] J. Aracena.  Maximum number of fixed points in regulatory boolean networks.  Bulletin of mathematical biology, 70(5):1398, 2008.
  * [5] C. Bazgan, Z. Tuza, and D. Vanderpooten.  Satisfactory graph partition, variants, and generalizations.  European Journal of Operational Research, 206(2):271–280, 2010\.
  * [6] H. Fernau and J. Rodriguez-Velazquez.  A survey on alliances and related parameters in graphs.  Electronic Journal of Graph Theory and Applications (EJGTA), 2(1):70–86, 2014.
  * [7] F. Fogelman, E. Goles, and G. Weisbuch.  Transient length in sequential iteration of threshold functions.  Discrete Applied Mathematics, 6(1):95–98, 1983.
  * [8] S. Frischknecht, B. Keller, and R. Wattenhofer.  Convergence in (social) influence networks.  In International Symposium on Distributed Computing, pages 433–446. Springer, 2013.
  * [9] C. Gao and Y. Dong.  ABS algorithm for solving a class of linear Diophantine inequalities and integer LP problems.  Journal of Applied Math. & Informatics, 26(12):349–353, 2008\.
  * [10] E. Goles and J. Olivos.  Periodic behaviour of generalized threshold functions.  Discrete Mathematics, 30(2):187 – 189, 1980.
  * [11] D. Irons.  Improving the efficiency of attractor cycle identification in boolean networks.  Physica D: Nonlinear Phenomena, 217(1):7–21, 2006.
  * [12] S. Kauffman et al.  The origins of order: Self-organization and selection in evolution.  Oxford University Press, USA, 1993.
  * [13] R. Královič.  On majority voting games in trees.  In L. Pacholski and P. Ružička, editors, SOFSEM: Theory and Practice of Informatics, pages 282–291, Heidelberg, 2001. Springer.
  * [14] M. Milano and A. Roli.  Solving the satisfiability problem through boolean networks.  In AI*IA 99: Advances in Artificial Intelligence, pages 72–83. Springer Berlin, 2000.
  * [15] S. Mishra and S. Rao.  Minimum monopoly in regular and tree graphs.  Discrete Mathematics, 306(14):1586–1594, 2006.
  * [16] P. Papp and R. Wattenhofer.  Stabilization Time in Minority Processes.  In $30^{th}$ Int. Symp. on Algorithms & Computation, volume 149 of LIPIcs, pages 43:1–43:19, Dagstuhl, 2019.
  * [17] D. Peleg.  Local majorities, coalitions and monopolies in graphs: a review.  Theoretical Computer Science, 282(2):231–257, 2002.
  * [18] S. Poljak and M. Sura.  On periodical behaviour in societies with symmetric influences.  Combinatorica, 3(1):119–121, 1983.
  * [19] J. Rouquier, D. Regnault, and É. Thierry.  Stochastic minority on graphs.  Theoretical Computer Science, 412(30):3947–3963, 2011.
  * [20] A. Veliz-Cuba and R. Laubenbacher.  On the computation of fixed points in boolean networks.  Journal of Applied Mathematics and Computing, 39:145–153, 2012\.
  * [21] A. Zehmakan.  On the Spread of Information Through Graphs.  PhD thesis, ETH Zürich, 2019.