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

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 [19] and the dominance problem, e.g., how many nodes must initially be black so that eventually all nodes are black [14]. 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 [8, 15]. 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)$ [5]. Frischknecht et al. showed that this bound is tight, up to some poly-logarithmic factor [6].

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) [10], 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 Sect. 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 [12]. 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. 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. 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. 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. A long version of the paper including all proofs is available [17].

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 [19] resp. [13]. Rouquier et al. study the minority process in the asynchronous model, i.e., not all nodes update their color concurrently [16]. 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 [11]. 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.

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 [18]. 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 [9]. Aracena determined the maximum number of fixed points in a particular class of BN called regulatory Boolean networks [4].

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., $\left|\mathcal {C}(G)\right|=2^{\left|V\right|}$. 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) = {\left\{ \begin{array}{ll} c(v) &{} \text {if } \left|N^{c(v)}(v)\right| \le \left|N^{1-c(v)}(v)\right|\\ 1-c(v) &{} \text {if } \left|N^{c(v)}(v)\right| > \left|N^{1-c(v)}(v)\right| \end{array}\right. }$$

$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 $\le$ 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}}$. Figure 1 depicts a sequence of colorings for $\mathcal {{MIN}}$.

Fig. 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 multichromatic.

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^*$ 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=\left|V\right|$. 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 $\mathcal{C}_T(F)$ and edges F. An edge of $(u,w)\in F$ connects components $T_1,T_2 \in \mathcal{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^*$ 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 $\varDelta$. 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 $\left|\mathcal {F}_{\mathcal {{M}}}(T)\right|$ in terms of n and $\varDelta$. 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}$

It is easy to see that 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 true in general 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 T for $\mathcal {M}$.

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)\ge 2$ and $deg_T(w)\ge 2$. Furthermore, $F_v\le deg_T(v)/2$ for each node v of T.

Proof

Assume $\mathcal {{M}}=\mathcal {{MIN}}$, the other case is proved similarly. Then $\left|N_T^{1-c(u)}(u)\right| \ge \left|N_T^{c(u)}(u)\right|\ge 1$ for $(u,w)\in F$. Thus, $deg_T(u) = \left|N_T^{c(u)}(u)\right| + \left|N_T^{1-c(u)}(u)\right|\ge 2$. Similarly $deg_T(w)\ge 2$. Let $v\in V$. Then $\left|N_T^{c(v)}(v)\right|\le \left|N_T^{1-c(v)}(v)\right|$ since $c\in \mathcal {F}_{\mathcal {M}}(T)$, i.e., $deg(v) \ge 2\left|N_T^{c(v)}(v)\right|= 2F_v$.   $\square$

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

Definition 1

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 \le deg(v)/2$ for each node v. $E_{fix}(T)$ denotes the set of all legal subsets of a tree T.

Theorem 1

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

Proof

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^*\in \mathcal {C}_T(F)$ with $v^*\in T^*$. Let $c_F(v^*)=0$ and extend $c_F$ to an independent coloring of $T^*$, e.g., by using breadth-first search. This uniquely defines $c_F$ on $T^*$. 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=\left|N_2\right|$. No node of $N_2$ has yet been assigned a color. By assumption we have $\left|N_2\right| \le deg_T(u)/2$. Hence, $\left|N_2\right| \le \left|N_1\right|$. 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 $\left|N_T^{c_F(u)}\right|\le \left|N_T^{1-c_F(u)}\right|$. 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^*$ and $u \in N_{T^*}(v)$. Then $c(u)\not =c(v)$, otherwise $u\not \in T^*$. Hence, $\mathcal {B}_T(F_c)$ is for $T^*$ independent. Since $c_{F_c}(v^*) = c(v^*)=0$ we have $\mathcal {B}_T(F_c)(v) = c(v)$ for all $v\in T^*$. Next we repeat this argument for all $\hat{T}\in \mathcal{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$.

   $\square$

Theorem 1 implies the following two results.

Corollary 1

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.

Corollary 2

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.

4.2 Counting Fixed Points

Theorem 1 allows to compute the number of fixed points in specific cases. If $\varDelta =n-1$ (resp. $\varDelta =n-2$) then $\left|\mathcal {F}_{\mathcal {MIN}}(T)\right|= 2$ (resp. $\left|\mathcal {F}_{\mathcal {MIN}}(T)\right|= 4$). Furthermore, $\left|\mathcal {F}_{\mathcal {MIN}}(T)\right|\le 8$ if $\varDelta =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^*$ 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^*$ to v in T are also colored. Secondly, if a neighbor of v other than the one closer to $v^*$ 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) -\left|N^{0}(v)\right| -\left|N^{1}(v)\right|$ 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:

$$ \left|N^{c(v)}(v)\right| + \hat{N}_{c(v)} \le \left|N^{1-c(v)}(v)\right| + \hat{N}_{1-c(v)}= \left|N^{1-c(v)}(v)\right| + r - \hat{N}_{c(v)}.$$

Hence,

$$\begin{aligned} \hat{N}_{c(v)} \le \frac{r + \left|N_{1-c(v)}(v)\right| -\left|N_{c(v)}(v)\right|}{2}. \end{aligned}$$

(1)

Let

$$\begin{aligned} r_0= \min \left( \lfloor (r +\left|N_{1-c(v)}(v)\right| -\left|N_{c(v)}(v)\right|)/2\rfloor , r\right) . \end{aligned}$$

(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} \left( {\begin{array}{c}r\\ i\end{array}}\right)$ 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 $\ge$ must be replaced by $\le$ and the assignment of colors to nodes in U is reversed.

Next we prove an upper bound for $\left|{F}_{\mathcal {{M}}}(T)\right|$. According to Corollary 1 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.

Lemma 2

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 $\left|\mathcal {F}_{\mathcal {{M}}}(T)\right|=\left|\mathcal {F}_{\mathcal {{M}}}(T^0)\right|+\left|\mathcal {F}_{\mathcal {{M}}}(T^1)\right|$.

Theorem 2

Let T be a tree and P a path. Then $\left|\mathcal {F}_{\mathcal {{M}}}(T)\right| \le 2F_{n-\lceil \varDelta /2\rceil }$ and $\left|\mathcal {F}_{\mathcal {{M}}}(P)\right|= 2F_{n-1}$.

Figure 2 shows that the bound of Theorem 2 is not sharp. Let $B_h$ be a binary tree of depth h. The equation $\left|\mathcal {F}_{\mathcal {M}}(B_h)\right| =\left|\mathcal {F}_{\mathcal {M}}(B_{h-1})\right|(\left|\mathcal {F}_{\mathcal {M}}(B_{h-1})\right| + 2\left|\mathcal {F}_{\mathcal {M}}(B_{h-2})\right|^2)$ already contained in [11] directly follows from Theorem 1.

Fig. 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 +\left|\mathcal {F}_{\mathcal {M}}(T)\right|\times \left|E^2(T)\right|)$. Since $\left|E^2(T)\right| \le n$ the running time is in $O(n\left|\mathcal {F}_{\mathcal {M}}(T)\right|)$. If $E^2(T)=\{e_1,\ldots ,e_l\}$ then 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.

Theorem 3

Algorithm 1 computes all $\left|\mathcal {F}_{\mathcal {M}}(T)\right|$ fixed points of a tree T in time $O(n +\left|\mathcal {F}_{\mathcal {M}}(T)\right|\times \left|E^2(T)\right|)$ using $O(\left|E^2(T)\right|\times \left|\mathcal {F}_{\mathcal {M}}(T)\right|)$ memory.

Proof

By Theorem 1 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=\left|E^2(T)\right|$. 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 $\left|S_1\right|=1$ and $\left|\mathcal {F}(T)^+\right|=\left|S_{l+1}\right|$.

Next we prove that $(4/5)\left|S_{i+1}\right|\ge \left|S_i\right|$ 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\le 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 $\left|S_i\right|=4n_1+2n_2+n_3$ and $\left|\hat{S}\right|=5n_1+3n_2+2n_3$. Since $S_{i+1}= \hat{S}$ we have $(4/5)\left|S_{i+1}\right|\ge \left|S_i\right|$. The overall number of executions of the inner foreach-loop is $\sum _{i=1}^l\left|S_i\right|$. Thus,

$$\sum _{i=1}^l\left|S_i\right| \le (4/5)\sum _{i=2}^{l+1}\left|S_i\right|= (4/5)\sum _{i=1}^{l}\left|S_i\right| + (4/5)(\left|S_{l+1}\right|-1).$$

Hence, $\sum _{i=1}^l\left|S_i\right| \le 4 (\left|S_{l+1}\right|-1) < 4 \left|\mathcal {F}(T)^+\right|$. 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(\left|X\right|)$.   $\square$

The bound $(4/5)\left|S_{i+1}\right|\ge \left|S_i\right|$ for all i can be used to prove the lower bound of $((5/4)^l$ with $l=\left|E^2(T)\right|$ for $\left|\mathcal {F}_{\mathcal {M}}(T)\right|$. We conjecture that a more detailed analysis of the relation between $\left|S_{i+1}\right|$ and $\left|S_{i}\right|$ 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\le b$. Here, A is a binary $\left|E^2(T)\right| \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 1 the set of fixed points corresponds to the solutions of $Ax\le b$. Unfortunately there isn’t much work available for solving systems of linear diophantine inequalities [7].

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 $\left|\mathcal {P}_{\mathcal {{M}}}(T)\right|$ 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 6 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}$, a corresponding result holds for $\mathcal {MAJ}$.

Lemma 3

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 $\left|N_t^{1-c(u)}(u) - N_t^{c(u)}(u)\right| \le N_f^{1-c(u)}(u) - N_f^{c(u)}(u)$ and a toggle node of c if and only if $\left|N_f^{c(u)}(u) - N_f^{1-c(u)}(u)\right| < N_t^{c(u)}(u) - N_t^{1-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 4 we give a characterization $\mathcal {P}_{\mathcal {M}}(T)$, it allows to generate all pure 2-cycles and compute $\left|\mathcal {P}_{\mathcal {M}}(T)\right|$.

Lemma 4

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.

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

Lemma 5

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)\ge 1$. Hence, $deg(u)= N^{c(u)}_T(u) + N^{1-c(u)}_T(u)\ge 3$. Similarly $deg(w)\ge 3$. Let $v\in T_u$. If $v\not =u$ then all neighbors of v in T are in $T_u$ and thus $\left|N^{c(u)}_{T_u}(u)\right| > \left|N^{1-c(u)}_{T_u}(u)\right|$. 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 $\left|N^{c(u)}_{T_u}(u)\right|=\left|N^{c(u)}_T(u)\right| > \left|N^{1-c(u)}_T(u)\right| = \left|N^{1-c(u)}_{T_u}(u)\right|+1$ we have $\left|N^{c(u)}_{T_u}\right| > \left|N^{1-c(u)}_{T_u}(u)\right|$. Hence, Lemma 4 implies that c induces a pure 2-cycle for $\mathcal {{MIN}}$ on $T_u$. The same is true for $T_w$.   $\square$

Corollary 3

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 \mathcal{C}_T(F_c)$ then $\left|\hat{T}\right|\ge 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 \mathcal{C}_T(F_c)$ then $\left|\hat{T}\right|\ge 3$ and c induces an independent coloring on $\hat{T}$. Furthermore, $(F_c)_v < deg_T(v)/2$ for $v\in V$.

Corollary 3 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 2

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 4

For a 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^*\in \mathcal {I}_0$. Assume $\mathcal {{M}}=\mathcal {{MIN}}$. Define a mapping $C_F: \mathcal{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^*)=0$. F uniquely defines $c_F$, since for each node v there is a unique $\hat{T} \in \mathcal{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 \mathcal{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 $\left|N_T^{c_F(v)}(v)\right| > deg(v)/2$. Thus, $2\left|N_T^{c_F(v)}(v)\right|> \left|N_T^{c_F(v)}(v)\right| +\left|N_T^{1-c_F(v)}(v)\right|$ and hence, $\left|N_T^{c_F(v)}(v)\right|>\left|N_T^{1-c_F(v)}(v)\right|$ for all v. Hence, $c_F\in \mathcal {P}_{\mathcal {MIN}}(T)^+$ by Lemma 4. 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 5 we have $F_c\in E^3(T)$. Let $v\in V$. Since c is a pure 2-cycle we have $\left|N_T^{c(v)}(v)\right|>\left|N_T^{1-c(v)}(v)\right|$, i.e., $deg(v) > 2\left|N_T^{1-c(v)}(v)\right|$. Since, $(F_c)_v =\left|N_T^{1-c(v)}(v)\right|$ 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 3 $\mathcal {B}_{pure}(F_c)$ is for each tree $\hat{T}\in \mathcal{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 \mathcal{C}_T(F)$ and in the second part we define $F_c=\{(u,w)\in E \;|\;c(u) = c(w)\}$.   $\square$

Corollary 4

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)\ge 3$ and $deg(w)\ge 3$.

Proof

We provide the proof for $\mathcal {M}=\mathcal {MIN}$. The result follows from Theorem 4. 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.   $\square$

Corollary 5

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.

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)$. Figure 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)$.

Fig. 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 4 allows to determine the pure 2-cycles of a tree T, and thus, $\left|\mathcal {P}_{\mathcal {M}}(T)\right|$. Since $E_{pure}(T) \subseteq E_{fix}(T)$ we have $\left|\mathcal {P}_{\mathcal {M}}(T)\right|\le \left|\mathcal {F}_{\mathcal {M}}(T)\right|$ and $\left|\mathcal {P}_{\mathcal {M}}(T)\right|\le 2F_{n-\lceil \varDelta /2\rceil }$ by Theorem 2. 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 + \left|\mathcal {P}_{\mathcal {M}}(T)\right|\left|E^3(T)\right|)$. Next we provide a better upper bound for $\left|\mathcal {P}_{\mathcal {M}}(T)\right|$. Let $e_T=\left|E^3(T)\right|$.

Lemma 6

Let T be a tree, then $e_T\le (n-4)/2$.

The last lemma implies $\left|\mathcal {P}_{\mathcal {M}}(T)\right|\le 2^{1+(n-4)/2}$. This bound is purely based on the bound for $\left|E^3(T)\right|$. 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 6 is sharp, but there is large gap between $\left|E^3(H_n)\right|$ and $\left|E_{pure}(H_n)\right|$.

Fig. 4.

The graph $H_{10}$, the three edges belonging to $E^3(H_{10})$ are depicted by solid lines. In general we have $\left|E^3(H_n)\right|=2^{(n-4)/2}$ and $\left|E_{pure}(H_n)\right|=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 3

Let T be a tree and $c\in \mathcal{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 hypertree $\mathcal {B}_c(T)$.

Lemma 7

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

Proof

We assume $\mathcal {M}=\mathcal {MIN}$. Let $T'$ be a connected component of $T^f$ and u a node of $T'$. With respect to T we have $\left|N_t^{1-c(u)}(u) - N_t^{(u)}(u)\right| \le N_f^{1-c(u)}(u) - N_f^{c(u)}(u)$ by Lemma 3. Restricting c to $T'$ gives $N_{T'}^{c(u)}(u)=N_f^{c(u)}(u)$ and $N_{T'}^{1-c(u)}(u)=N_f^{1-c(u)}(u)$. Thus, $N_{T'}^{1-c(u)}(u) \ge N_{T'}^{c(u)}(u)$ and u is a fixed node of $T'$ for c. Hence, c is a fixed point for $T'$. The result about components of $T^t$ is proved similarly.    $\square$

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

Definition 4

Let T be a tree, $c\in \mathcal{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 $\left|T_i\right|\ge 2$, since all neighboring blocks are fixed blocks. Fixed blocks can consist of a single node only (see Fig. 6).

Fig. 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.

Fig. 6.

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

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 4, i.e., the trees $T_B$ for which there exists $c\in \mathcal{C}^2_{\mathcal {M}}(T)$ such that $T_B=\mathcal {B}_c(T)$. The following theorem summarizes properties of 2-cycles.

Theorem 5

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. If $deg_T(u)=2$ then u is a fixed node.

• 2. $\min (deg_T(u),deg_T(w))\ge 2$ and $\max (deg_T(u),deg_T(w))\ge 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. 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. Assume that u is toggle node. Then $\left|N^{c(u)}(u)\right| > \left|N^{1-c(u)}\right|$. Thus, if $\left|N^{1-c(u)}\right|> 0$ then $deg_T(u)\ge 3$. Therefore, $\left|N^{1-c(u)}\right|=0$ and $\left|N^{c(u)}(u)\right|=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))\ge 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 3 we have $N_f^{1-c(v)}=N_f^{c(v)}$ thus, $deg_T(v)= 1 + 2 N_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 3 yields that $deg_T(v)$ is even.   $\square$

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 5

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 \mathcal{C}_T(F)$ is called fixed if $\left|\hat{T}\right|=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 $\mathcal{C}_T(F)$.

Definition 6

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 \mathcal{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 8

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 5.2 we have $F_c \subseteq E^{\,2.5}(T)$. By construction of $\mathcal {B}_c(T)$ and Theorem 5.4 and 5.3 we have $Fix(T,F_c)\subseteq \mathcal {I}_0(\mathcal {T}_{F_c})$. Theorem 5.4 completes the proof.   $\square$

Definition 7

Let T be a tree. A coloring $c\in \mathcal{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 \mathcal{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 9

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. The proof is by induction on $\left|F\right|$. The case $\left|F\right|=0$ is obvious, c is the monochromatic coloring. Let $\left|F\right|>0$. Let $L\in \mathcal {T}_{F}$ be a leaf and $e=(u,w)\in F$ such that $w\in L$. Then $\left|L\right|\ge 2$ if $L\in \mathcal {I}_0(\mathcal {T}_F)$ and $\left|L\right|\ge 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 $\left|L\right| > 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 $\left|\tilde{T}\right| < \left|T\right|$. 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 $\mathcal{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 \mathcal{C}_{\tilde{T}}(F)$. Then, $T_0\in \mathcal{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 \mathcal{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 \mathcal{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 $\left|L\right| = 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 \mathcal{C}_{{T}}({F})$ with $u\in T_u$. Then $T_u \in \mathcal {I}_1(\mathcal {T}_F)$ and thus, $\left|T_u\right|>1$, $deg_{T_u}(u)\ge 1$ and $deg_{T}(u)\ge 3$. Let $\tilde{T}_u \in \mathcal{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 \mathcal{C}_{\tilde{T}}(\tilde{F})$ with $\left|T_0\right|=1$. Then $T_0 \in \mathcal{C}_{{T}}({F})$, thus $deg_T(v_0)\equiv 0(2)$. Hence, $deg_{\tilde{T}}(v_0)\equiv 0(2)$. Let $\hat{T}\in \mathcal{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 \mathcal{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 3 we have $\left|N_f^{\tilde{c}(u)}(u) - N_f^{1-\tilde{c}(u)}(u)\right| < 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 3 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, $\left|N_f^{c(u)} - N_f^{1-c(u)}\right| =1 < N_t^{{c}(u)}(u)$. Therefore, c has the desired properties.   $\square$

Theorem 6

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.

Corollary 6

Let T be a tree where all nodes have odd degree. Then $E_{block}(T) = \{ F\subseteq E^{3} (T) \;|\;\mathcal{C}_T(F) \text { does not contain a component of size } 1\}$. Let P be 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 example in [17]). Since $E_{block}(T) \subseteq E_{fix}(T)$ each upper bound for $\left|\mathcal {F}_{\mathcal {M}}(T)\right|$ is also an upper bound for $\left|\mathcal {C}^2_{\mathcal {M}}(T)\right|$. 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 Definition 6.

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 $\left|\mathcal {F}_{\mathcal {M}}(T)\right|$ and $\left|\mathcal {P}_{\mathcal {M}}(T)\right|$ 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 $\left|E_{fix}(T)\right|$ and $\left|E_{pure}(T)\right|$ for these trees.