# Solutions to All-Colors Problem on Graph Cellular Automata

Authors: Xiaoyan Zhang; Chao Wang
Journal: Complexity
 (2019)

---

## Abstract

The All-Ones Problem comes from the theory ofσ+-automata, which is related to graph dynamical systems as well as the Odd Set Problem in linear decoding. In this paper, we further study and compute the solutions to the “All-Colors Problem,” a generalization of “All-Ones Problem,” on some interesting classes of graphs which can be divided into two subproblems: Strong-All-Colors Problem and Weak-All-Colors Problem, respectively. We also introduce a new kind of All-Colors Problem, k-Random Weak-All-Colors Problem, which is relevant to both combinatorial number theory and cellular automata theory.


---

## Body

## 1. Introduction

A graph dynamical system (GDS) is a dynamical system constructed over a graph whose vertices can have different states, such that all these states together at a given time constitute a state of the system which can evolve according to an updating scheme [1, 2]. The states of the vertices are commonly modeled by the Boolean values 0 and 1, while the updating scheme consists of as many local functions as vertices and a series of rules that indicate the order in which the local functions act. GDS can be divided into two categories: parallel (PDS) [3, 4] and sequential (SDS) [5, 6] when all the local functions act synchronously or follow an order to act, respectively. In the specific literature, other related topics appeared previously, such as Boolean networks (BN) [7] and cellular automata (CA) [8], which are, in fact, particular cases of GDS. In this paper we will consider “All-Colors Problem,” which is concerned with graph cellular automata as one kind of dynamical systems on networks.A graph is a pairG=(V,E) where E⊆V×V. These structures allow for self loops. In the theory of automata, we will insist that G is local finite; i.e., every vertex in G is adjacent to only finite many vertices. In this paper, we only consider G as a finite simple graph. It is convenient to identify E with the adjacency matrix of G constructed as a matrix in ∏V×VF2. Here F2=0,1 is the two-element field and there is a 1 in the uth row and vth column of E if and only if there is a directed edge from vertex u to vertex v in G.A vertexu is a predecessor of v if there exists an edge (u,v) in G. The collection of all predecessors of v will be denoted by(1)ΓGv=u∈V∣u,v∈E.Note that ΓG(v) may or may not include v depending on whether v has a self-loop in G or not. We will refer to ΓG(v) as theneighborhood of v in G. Aconfiguration of G is a function(2)X:V→F2.The collection of all configurations of G will be denoted by CG. Define thetransition ruleσG:CG→CG by(3)σXv≔∑u∈ΓvXumod2.A=(G,σG) is called the σ-automaton on G.Configurations are conveniently identified with subsets ofV; i.e., X is identified with {v∈V∣X(v)=1}. Observe that algebraically CG is a vector space over F2, CG=∏VF2; addition here amounts to take symmetric differences. We will call this space theconfiguration space. Furthermore, σ is a linear map from the configuration space to itself (such rules are called additive in [9]). If one thinks of configuration X as a column vector over F2, it is obvious from the definition that σ(X)=E·X where E is the adjacency matrix of G.Aσ-automaton A=(G,σG) issymmetric if and only if the adjacency matrix E of G is symmetric; thus symmetric σ-automata arise from undirected graphs. In the following sections, we will consider only symmetric σ-automata on undirected graphs.LetG be an undirected graph without self-loops and D a subset of V. Define G(D) to be the graph obtained from G by adding self-loops at all vertices in D. σ-automata of the form (G,σG(V)) or (G,σG(∅)) are calledLindenmayer automata on G.To lighten notation we will usually omit the subscriptG and write Γ(v), σ and (G,σ), and so forth. Also we will write σ+ for σG(V) and σ- for σG(∅). We will write 0 for the empty set and 1 for V as members of CG, so 0(v)=0 and 1(v)=1 for all v in V.The termAll-Ones Problem was introduced by Sutner; see [10]. It has applications in linear cellular automata; see [11] and the references therein. The problem is cited as follows: suppose each of the vertices of an undirect graph with n vertices is equipped with an indicator light and a button. If the button of a vertex is pressed, the light of that vertex will change from off to on and vice versa; the same happens to the lights of all the edge-adjacent vertices. Initially all lights are off. Now, consider the following questions: is it possible to press a sequence of buttons in such a way that in the end all lights are on? This is referred as theAll-Ones Problem. If there is such a way, how to find a such way? Here and in what follows, we consider connected simple undirected graphs only. When disconnected graphs must be concerned, we can deal with them component by component. For all terminology and notations on graphs, we refer to [12]. An equivalent version of the All-Ones Problem was proposed by Peled in [13], where it was called theLamp Lighting Problem. We cite it as follows.Light bulbs L 1 , L 2 , … , L n are controlled by switches S 1 , S 2 , … , S n . Switch S i changes the on/off status of light L i and possibly the status of some other lights. Assume that if S i changes the status of light L j , then S j changes the status of light L i . Initially all the lights are off. Prove that it is possible to operate the switches in such a way that all the lights are on.The rule of the All-Ones Problem isσ+-rule on graphs, which means that a button lights not only its neighbors but also its own light Li. If a button lights only its neighbors but not its own light, this rule on graphs is called σ--rule. There were many publications on the All-Ones Problem; see Sutner [14, 15], Barua et al. [16], and the references therein. Using linear algebra, Sutner [17] proved that it is always possible to light every lamp in any graphs by σ+ rule. Lossers [18] gave another beautiful proof also by using linear algebra. A graph-theoretic proof was given by Erikisson et al. [19]. More results and related references can be referred to [20–25].In graph-theoretic terminology, a solution to the All-Ones Problem withσ+-rule can be stated as follows: given a graph G=(V,E), where V and E denote the vertex-set and the edge-set of G, respectively, a subset X of V is a solution if and only if for every vertex v of G the number of vertices in X adjacent to or equal to v is odd. Such a subset X is called anodd parity cover in [17]. So, the All-Ones Problem can be formulated as follows: given a graph G=(V,E), does a subset X of V exist such that, for any vertex v∈V-X, the number of vertices in X adjacent to v is odd, while for any vertex v∈X, the number of vertices in X adjacent to v is even?Sutner [10] proposed the question whether there is a graph-theoretic method to find a solution for the All-Ones Problem for trees. Galvin [26] solved this question.The “All-Ones Problem” can be considered to find the preimages of configuration1 under parallel map defined by local rule σ. In this paper, we further study the “All-Colors Problem,” a natural generalization of “All-Ones Problem,” which can be divided into two subproblems: Strong-All-Colors Problem and Weak-All-Colors Problem, respectively.This paper is organized as follows. In Section2, we introduce the preliminary and definitions of the “All-Colors Problem” under σ+-rule. The “All-Colors Problem” can be divided into two subproblems: Strong-All-Colors Problem and Weak-All-Colors Problem which are studied in Sections 3 and 4, respectively. In the end of Section 4, we also introduce a new kind of All-Color Problem, k-Random Weak-All-Colors Problem, which is relevant to both combinatorial number theory and cellular automata theory.


## 2. Preliminary of All-Colors Problem

Here we introduce a natural generalization for the All-Ones Problem—All-Colors Problem. When we discuss the All-Colors Problem, we need a positive integer m>2 and a graph G each of whose vertices has a color value between 0 and m-1. There are two kinds of All-Colors Problem: Strong-All-Colors Problem and Weak-All-Colors Problem. We give their accurate definitions as follows.Definition 1 (strong-all-colors problem underσ+-rule on Zm).
If a vertex is pressed one time, then the color values of the vertex and its neighbors are added by1 under the meaning of modular m. If the initial status is that the color value of every vertex is 0, then how to press some vertices (maybe many times) to make the color value of every vertex equal to 1 under the meaning of modular m.Definition 2 (weak-all-colors problem underσ+-rule on Zm).
If a vertex is pressed one time, then the color values of the vertex and its neighbors are added by1 under the meaning of modular m. If the initial status is that the color value of every vertex is 0, then how to press some vertices (maybe many times) to make the color value of every vertex not equal to 0 under the meaning of modular m.A solution to the Strong-All-Colors Problem on a graphG under σ+-rule is a configuration f:V(G)→Zm such that, for any v∈V(G),(4)∑w∈Nv∪vfw=1modm, where N(v) is denoted as the set of vertices of G which are adjacent to w. Correspondingly, a solution to the Weak-All-Colors Problem on a graph G under σ+-rule is a configuration f:V(G)→Zm such that, for any v∈V(G),(5)∑w∈Nv∪vfw≠0modm.It is worth noting that we only need to study the Strong-All-Colors Problem and the Weak-All-Colors Problem in the case thatm is a power of a prime. Indeed, let m=∏i=1rpiei be the prime factorization of m. Suppose that there exists a solution ci:V(G)→Zpiei to the Strong-All-Colors Problem under σ+ on Zpiei for any i. That is, for any v∈V(G),(6)∑w∈NGv∪vciw=1modpiei.By the Chinese Remainder Theorem, there exists c:V(G)→Zm such that(7)cv=civ=1modpieifor any i∈{1,…,r} and v∈V(G). It follows that(8)∑w∈NGv∪vcw=1modpiei,for any v. By the Chinese Remainder Theorem again, one has(9)∑w∈NGv∪vcw=1modm.That is, c is a solution to the Strong-All-Colors Problem on Zm. The discussion of the Weak-All-Colors Problem is similar.Note that we can also define the correspondingStrong-All-Colors Problem under σ--rule on Zm andWeak-All-Colors Problem under σ--rule on Zm; however, they are more difficult to study.In the following sections, we will discuss the All-Colors Problem underσ+-rule in detail. We need to use two definitions equivalent to Definitions 1 and 2 for convenience. Suppose G is a simple undirected graph; each vertex of G has a color value on Zm which can change with time. These changes abide by the following rules (σ+-rule): If, for ∀v∈G, c0(v) is the initial color value of v at time t=0, then, at time t=1, the color value of v has changed to c1(v)=∑u∈N(v)∪{v}c0(u), where N(v) is the set of vertices which are adjacent to v.The Strong-All-Colors Problem underσ+-rule can be redefined as follows:to find the initial color values of all the vertices ofGat timet=0such that any vertex ofGhas a color value equal to1(modm)at timet=1underσ+-rule.The Weak-All-Colors Problem can be redefined as follows:to find the initial color values of all the vertices ofGat timet=0such that no vertex ofGhas a color value equal to0(modm)at timet=1underσ+-rule.For the sake of simplicity, the Strong-All-Colors Problem is denoted as SACP from now on. Correspondingly, the Weak-All-Colors Problem is denoted as WACP.


## 3. Strong-All-Colors Problem underσ+-Rule on Zm

First of all, for a general graph, the SACP withσ+-rule on Zm may have no solution. For example, there is no solution to the SACP under σ+-rule on Zm for a circle Cn when 3∤n and 3∣m. Particularly, by observing the following tree T0 with 6 vertices, in Figure 1, we will discover surprisingly that there is no solution to the SACP under σ+-rule on Zm for any m≥3.Figure 1
A tree without solution to the SACP form≥3.Then a question arises naturally: How to determine whether a graph has a solution to the SACP withσ+-rule on Zm?It is easy to find an algebraic method to solve this problem. SupposeG is a graph with n vertices. The following theorem can be obtained easily and we omit the proof.Theorem 3.
There exists a solution to the SACP withσ+-rule on Zm(m≥2) for a graph G if and only if the following system of linear equations has a solution on Zm.(10)A+IX=1modm,where A is the adjacent matrix of G, I is the identity matrix, X is an n×1 vector of variables, and (1)(modm) is an n×1 vector each element of which is 1(modm).Example 4.
Consider the treeT0 at the beginning of this section. Its adjacent matrix is(11)A=001000001000110100001011000100000100.
It is easy to verify that(12)A+Ix1x2⋮xn=1modm1modm⋮1modmis equivalent to(13)x1+x3=1modm1x2+x3=1modm2x1+x2+x3+x4=1modm3x3+x4+x5+x6=1modm4x4+x5=1modm5x4+x6=1modm6Let us operate the 6 equations as follows.(14)1+2+5+6-3-4,so we get(15)0=2modmIt is obvious that equation (15) holds if and only if m=2. So T0 has no solution to the SACP under σ+-rule on Zm for m≥3, which we have just declared.The system of linear equations overZm could be solved. Let A∈Rn×n, B∈Rn×1, and X=(x1,…,xn)T. We need to solve the equation AX=B. If R, as Zm above, is a principle idea ring, there exist invertible matrices U,V∈Mn(R) such that A=UCV, where(16)C=d10⋯00d2⋯0⋮⋮⋱⋮00⋯dn,where di∣di+1 and C is the Smith normal form of A. We can compute U and V if R=Zm. Then AX=B is equivalent to CVX=U-1B. We set Y=VX and we can solve CY=U-1B since C is a diagonal matrix. Hence, we obtain X=V-1Y.Although this algebraic method is quite succinct, it is interesting to study the SACP underσ+ rule on Zm over some classes of graphs.In the following, we consider the SACP underσ+-rule on Zm for trees. Note that we do all the operations “+” and “−” on the ring Zm. Consider the special case when the tree is a “caterpillar.” A tree T is called acaterpillar if and only if the remainder of T is a path after removing all the leaves of T. Figure 2 shows such a caterpillar.Figure 2
A caterpillarT.We can find the solution to the SACP underσ+-rule on Zm for a caterpillar T according to the following process.SupposeT is a caterpillar with the following shape of Figure 2. First we assume that the initial color value of vertex v1 is x, which will be determined in the end. It is easy to see that the initial color values of the leaves of vertex v1 must be 1-x in order to make the color values of vertices u11,u12,…, u1r1 changing to 1 by the meaning of modular m under σ+-rule. Then the initial color value of v2 would be -(r1-1)(1-x) to make the color value of v1 equal to 1 under σ+-rule. Repeat this step until we have determined the initial color value of vn, denoted by fn(x), which is a linear function of x. From this procedure we can see that there is only one equation to be satisfied; i.e.,(17)fn-1x+fnx+rn·1-fnx=1modm,where fn-1(x) is the initial color value of vertex vn-1.So we have the following.Theorem 5.
A caterpillarT has a solution to the SACP under σ+-rule on Zm if and only if the equation (17) has a solution on Zm.We give two examples with solutions to the SACP underσ+-rule on Zm in Figure 3. All the negative integers that appeared in the following figures are under the meaning of modular m.Figure 3
Two examples with solutions to the SACP onZm.As an application of Theorem5, we have the following.Corollary 6.
IfT is a path with n vertices, then T has a solution to the SACP under σ+-rule on Zm for any m≥2.Proof.
Letx1x2⋯xn, a sequence of integers on Zm, represent the initial color values of vertices of T. It is easy to check that(18)x1x2⋯xn=100100⋯10010,ifn≡2mod3100100⋯1001,ifn≡1mod3010010⋯010,ifn≡0mod3is a solution to the SACP under σ+-rule on Zm for any m≥2.Corollary 7.
IfT is a tree with the shape as shown in Figure 4, then(1)
whenk≡2(mod3), T has a solution as in Figure 5(2)
whenk≡1(mod3), T has a solution if and only if (pq-1)x≡q-1(modm) has a solution on Zm, which is equivalent to gcd(pq-1,m)∣(q-1). Here x is the initial color value of vertices u1,…,up(3)
whenk≡0(mod3), T has a solution if and only if (pq-p-q)x≡-q(modm) has a solution on Zm, which is equivalent to gcd(pq-p-q,m)∣q. The meaning of x is the same to aboveFigure 4
The shape of a special kind of caterpillars.Figure 5
A solution forT when k≡2(mod3).Now we show a reduction technique. First we introduce a new concept.Definition 8.
SupposeG is a graph. If there are 3 distinct vertices v1, v2, v3 of G satisfying (1)
v3 is a leaf(2)
v2 is exactly adjacent to v1 and v3
then{v1,v2,v3},{(v1,v2),(v2,v3)} is called a 3-connected path and denoted by (v1,v2,v3) simply.Example 9.
For example, Figure6 shows a tree which has a 3-connected path marked by an ellipse.Figure 6
An example of a 3-connected path.Theorem 10 (deleting a 3-connected path).
Suppose thatG is a graph with n vertices v1,v2,…,vn. If G contains a 3-connected path (vi1,vi2,vi3), then G has a solution to the SACP under σ+-rule on Zm if and only if G∖{vi1,vi2,vi3} has a solution to the SACP under σ+-rule on Zm, where G∖{vi1,vi2,vi3} is a tree or a forest.Proof.
SupposeT has a solution to the SACP under σ+-rule on Zm. Assume the initial color value of vertex vi is xi(1≤i≤n). We have xi1=0(modm) because it requires x2+x3=1(modm) and x1+x2+x3=1(modm) to ensure the color value of v2 and v3 to be changed to 1 under σ+-rule. Then we can say that (x4,x5,…,xn) is a solution to the SACP under σ+-rule on Zm for G∖{v1,v2,v3}.
For the converse, suppose(x4,x5,…,xn) is a solution to the SACP under σ+-rule on Zm for G∖{v1,v2,v3}. Let N~(vi1) denote the set of vertices G∖{v1,v2,v3} that are adjacent to vi1 in T. It is easy to check (x1′,x2′,…,xn′) is a solution to the SACP under σ+-rule on Zm for T, where(19)xj′=xj1≤j≤nandj≠1,2,30j=11-∑u∈N~vi1xuj=2∑u∈N~vi1xuj=3 This completes the Proof.It is worth noting that we can use this reduction technique repeatedly. For example, the tree in Example9 can be reduced continuously. The reduction process and its inverse, which can help us to get the solution to the SACP, are shown in Figure 7.Figure 7
Reduction to get the solution.In fact, there are some other complex structures which can be reduced. But they are commonly relevant toZm. For example, when m=3, the structures shown in Figure 8 can be removed from a tree, just like the 3-connected path.Figure 8
Complex structures that can be reduced whenm=3.Next, we study another special kind of trees—radioactive trees. A treeT is called aradioactive tree if and only if there is only at most one vertex of T which has a degree bigger than 2. In fact, a radioactive tree can be viewed as several paths adhering to a common vertex.Theorem 11.
IfT is a radioactive tree, then T has a solution to the SACP under σ+-rule on Zm for any m≥2.Proof.
Assume thatT has the shape shown in Figure 9.
By Theorem10 we can delete 3-connected path continuously. Without loss of generality we may assume that at last T has changed to T′ that has k′≤k paths from the root. It is enough to prove that T′ has a solution to the SACP. Suppose ri=1 for 1≤i≤s and ri=2 for s+1≤i≤k′ in T′. If s=k′, then xv=1, xui,1=0 for 1≤i≤s=k′ is a solution. If s<k′, then xv=0, xui,1=1 for 1≤i≤s, xui,1=0 and xui,2=1 for s+1≤i<k′, xuk′,1=1-s(modm) and xuk′,2=s(modm) is a solution to the SACP. The schematic diagram for the latter case is shown in Figure 10.Figure 9
A radioactive tree.Figure 10
The answer to the SACP for simplified treeT′ when s<k′.Actually, we can also prove Theorem11 with the help of our reduction technique introduced before. The detail of the proof is omitted here.


## 4. Weak-All-Colors Problem

In this section, we will study the WACP underσ+-rule on Zm, m≥2. It is worth noting when m=2, the WACP becomes the All-Ones Problem which we have discussed before. So the WACP is another generalized form of All-Ones Problem. The WACP has corresponding linear algebraic representation. If G is a graph with n vertices and A is the adjacent matrix of G, then the WACP is equivalent to the next algebraic question:Find the values ofn variables x1,x2,…,xn on Zm such that no component of the n×1 result vector of(20)A+Ix1x2⋮xn is equal to 0.It is known that any graphG has a solution to the All-Ones Problem under σ+-rule. We conjecture that it also holds for the WACP.Conjecture 12.
For any graphG, there is a solution to the WACP under σ+-rule on Zm(m≥2).We should point out that the original proof to the existence of a solution to the All-Ones Problem for any graphG cannot do any effects on the WACP on Zm when m≥3. So it seems that we need to find another approach to solve this conjecture.In this section, we emphasize the trees by using the technique of increasing a leaf. By Theorem14, we show that Conjecture 12 is valid for trees. By Theorem 15, it also holds for cycles. Using the increasing technique and Theorem 15, we prove that Conjecture 12 is valid for unicyclic graphs, which is Corollary 16. Furthermore, by Theorem 17, it is interesting that we can find a solution, which contains only 0 and 1, to the WACP under σ+-rule on Z3 for trees. Correspondingly another Conjecture 18 is proposed.Lemma 13 (increasing a leaf).
IfG is a graph and v is a vertex of G whose degree is 1, i.e., v is a leaf, then G has a solution to the WACP under σ+-rule on Zm(m≥3) if G∖{v} does too.Proof.
AssumeG∖{v} has a solution c0 to the WACP under σ+-rule on Zm. Suppose v is only adjacent to w in G. Then let(21)c0′v∈Zm∖-∑u∈Nw∪wc0u,-c0w,c0′u=c0u,ifu≠v.Because m≥3, so we could find a c0′(v) in Zm∖{-∑u∈N(w)∪{w}c0(u),-c0(w)}. It is easy to check that c0′ is a solution to the WACP under σ+-rule on Zm.
The proof is completed.From Lemma13, we can obtain Theorem 14 easily.Theorem 14.
LetT be a tree and v∈V(T). Then T has a solution c0 to the WACP under σ+-rule on Zm(m≥3) satisfying c0(v)=1.Proof.
We use the technique of increasing a leaf. Firstly letT1={v} be a one-vertex tree, and let c^1(v)=1, which is a solution to the WACP under σ+-rule on Zm satisfying c^1(v)=1. Secondly we can add another vertex u, which is adjacent to v, and the edge (u,v) into T1. Let T2 denote the new tree. It is easy to see that there is a solution c^2 to the WACP under σ+-rule on Zm satisfying c^2(v)=1. Repeat these steps by adding an appropriate vertex each time, until at last we get a solution c^n to the WACP under σ+-rule on Zm for T satisfying c^n(v)=1, which is just c0 that we want. We conclude the proof.Since it is not hard to construct a solution, we can obtain the following theorem straightforwardly.Theorem 15.
There is a solution to the WACP underσ+-rule on Zm(m≥3) for any cycle.In fact we can extend the result to “unicyclic graphs." Recall that a graphG is called unicyclic if it contains a unique cycle. In other words, we can regard a unicyclic graph as a cycle attached with each vertex a rooted tree.Corollary 16.
IfG is a unicyclic graph, then there is a solution to the WACP under σ+-rule on Zm(m≥3) for G.Proof.
From Theorem15, a cycle has a solution to the WACP under σ+-rule on Zm. Using the increasing technique repeatedly, we can prove that this statement holds.Next, we prove that there is a special solution to the WACP onZ3 for any tree such that all the color values of vertices are 0 and 1.Theorem 17.
IfT is a tree, then there is a solution c0 to the WACP under σ+-rule on Z3 such that c0(v)=0 or 1 for any v∈V(T).Proof.
SupposeT is a rooted tree with root t. We need to introduce three new concepts.
Thesmall WACP is to find an initial color value array c on T such that (1)
c(v)=0or1,∀v∈T(2)
∑v∈N(u)∪{u}c(v)≠0(mod3),∀u≠t(3)
∑v∈N(t)∪{t}c(v)=0 or 1(mod3)
Then the initial color value arrayc will be called a solution to the small WACP.
Correspondingly, thepositive WACP is to find an initial color value array c on T such that (1)
c(v)=0 or 1,∀v∈T(2)
∑v∈N(u)∪{u}c(v)≠0(mod3),∀u≠t(3)
∑v∈N(t)∪{t}c(v)=1 or 2(mod3)
Then the initial color value arrayc will be called a solution to the positive WACP.
Theeven WACP is to find an initial color value array c on T such that (1)
c(v)=0 or 1,∀v∈T(2)
∑v∈N(u)∪{u}c(v)≠0(mod3),∀u≠t(3)
∑v∈N(t)∪{t}c(v)=0 or 2(mod3)
Then the initial color value arrayc will be called a solution to the even WACP.
In fact a solution to the positive WACP is also a solution we required in this proposition. So it is sufficient for us to prove that there is a solution to the positive WACP for any rooted tree.
SupposeT is a rooted tree with root t. If there is a solution c to the small WACP such that c(t)=0, we say that 0 is a permissible color value of root t to the small WACP. Accordingly, if there is a solution c to the small WACP such that c(t)=1, then 1 is a permissible color value of root t to the small WACP. We name the set of all permissible color values of root t as thepermission set of roottto the small WACP and denote it by S.
Similarly, we can definethe permission set of roottto the positive WACP, denoted by P, andthe permission set of roottto the even WACP, denoted by E. Then for the rooted tree T with root t, (S,P,E) will be called thetype of root t and corresponding rooted tree T. For example, the type of a rooted tree shown in Figure 11 is ({1},{0,1},{0,1}), or denoted by (1,01,01) for simplicity.
Next we need to define “Add Into Operation.” Suppose T1 and T2 are two rooted trees with roots t1 and t2, respectively. We will get a new rooted tree with root t2 by adding T1 into T2 with t1 as a child of t2. This operation is called anAdd Into Operation onT1toT2. If the result tree is T3, then we denote the operation as T1⋗T2→T3. It is not difficult to show that each rooted tree can be derived by doing an Add Into Operation on one smaller rooted tree to another smaller rooted tree.
Furthermore, if the color value arrayc(0,S)1 on T1 is a solution to the small WACP for T1 and c(1,S)2 on T2 is a solution to the small WACP for T2, then the color value array c3=c(0,S)1∪c(1,S)2 will be a solution to the small WACP for T1⋗T2, i.e., a new tree with root t2, so we write c3 as c(1,S)3. Then we denote it as the equation(22)c0,S1⋗c1,S2→c1,S3. Similarly, we can get other equations like this. Altogether there are 15 equations as follows. (23)c0,S1⋗c1,S2→c1,S3,c0,S1⋗c1,P2→c1,P3,c0,S1⋗c1,E2→c1,E3,c1,S1⋗c1,S2→c1,P3,c1,S1⋗c1,P2→c1,E3,c1,S1⋗c1,E2→c1,S3,c0,P1⋗c0,S2→c0,S3,c0,P1⋗c0,P2→c0,P3,c0,P1⋗c0,E2→c0,E3,c1,P1⋗c0,S2→c0,P3,c1,P1⋗c0,P2→c0,E3,c1,P1⋗c0,E2→c0,S3,c0,E1⋗c1,S2→c1,S3,c0,E1⋗c1,P2→c1,P3,c0,E1⋗c1,E2→c1,E3.
From the above equations, we can calculate the type of the rooted treeT3 obtained from the Add Into Operation on a rooted tree T1 to another rooted tree T2, as long as we have known the types of T1 and T2. For example, if the root of T1 has the type (01,1,0) and the root of T2 has the type (01,01,1), then the type of the new result rooted tree derived by doing an Add Into Operation on T1 to T2 will be (1,01,01). The validity lies in the following 5 equations. (24)c0,S1⋗c1,S2→c1,S3,c1,P1⋗c0,S2→c0,P3,c0,E1⋗c1,P2→c1,P3,c1,P1⋗c0,P2→c0,E3,c0,E1⋗c1,E2→c1,E3.
Then we want to list all possible types of rooted trees. In fact, there are only8 distinct types of rooted trees. Each type and one of its representative rooted trees are shown in Figure 12.
In order to show that there are only8 distinct types, we need to show that the following assertion is correct.
Assertion. If each of the two rooted trees T1, T2 with roots t1 and t2, respectively, belongs to one of the 8 types, then the rooted tree T derived by doing an Add Into Operation on T1 to T2 belongs to one of the 8 types.
We have mentioned before how to calculate the type of the result rooted tree obtained by doing the Add Into Operation on a rooted tree to another if their types are known. Since all rooted trees can be derived by doing an Add Into Operation on a smaller rooted tree to another smaller one, we can observe that all the types of rooted trees are contained in the set of8 distinct types above. The proof of the Assertion exists in Table 1. Since the original table is too wide, we divide it into two tables as in Tables 1(a) and 1(b).
We have showed that any rooted tree belongs to one of the8 types and, in each of the 8 types, the permission set to the positive WACP is not empty. So any rooted tree would have a solution c to the positive WACP, which finishes the proof.Table 1
The result table of types of a new rooted tree derived by doing an Add Into Operation on a rooted treeT1 which has the type in the first left column to a rooted tree T2 which has the type in the first top row.
(a) ( 01,1 , 0 ) ( 01,01,1 ) ( 1,01,01 ) ( 01,1 , 01 ) ( 01,1 , 0 ) ( 01,01,1 ) ( 1,01,01 ) ( 01,1 , 01 ) ( 01,01,1 )  ( 01,01,1 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 1,01,01 ) ( 0,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 01,1 , 01 ) ( 01,01,1 ) ( 1,01,01 ) ( 01,1 , 01 ) ( 01,01,1 )  ( 0,01,01 ) ( 01,01,0 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 01,0 , 01 ) ( 01,1 , 01 ) ( 01,01,1 ) ( 1,01,01 ) ( 01,1 , 01 )  ( 01,01,0 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  (b) ( 0 , 01 , 01 ) ( 01 , 0 , 01 ) ( 01 , 01 , 0 ) ( 01 , 01 , 01 ) ( 01,1 , 0 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 01,01,1 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 1,01,01 ) ( 01,0 , 01 ) ( 01,01,0 ) ( 0,01,01 ) ( 01,01,01 )  ( 01,1 , 01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 0,01,01 ) ( 0,01,01 ) ( 01,0 , 01 ) ( 01,01,0 ) ( 01,01,01 )  ( 01,0 , 01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 01,01,0 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )  ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 ) ( 01,01,01 )Figure 11
A little tree with roott and its solutions to the three kinds of WACP, which show that the type of it is (1,01,01).Figure 12
All possible types of rooted trees.From Theorem17, we will think whether there is a solution to the WACP when m≥4, which is the following conjecture.Conjecture 18.
LetT be a tree. Then T has a solution to the WACP under σ+-rule on Zm(m≥4) such that c0(v)=0 or 1, ∀v∈T.In the following, we will put forward a special WACP underσ+-rule on complete graphs.LetKn be a complete graph with n vertices v1,v2,…,vn. Each vertex vi has an initial color value c0(vi) on Zm at time t=0. Suppose, at time t=1, the color value of each vertex vi, denoted by c1(vi), is equal to the sum of the color values of random m vertices under the meaning of modular m, i.e.,(25)c1vi∈c0vj1+c0vj2+⋯+c0vjmmodm∣j1,j2,…,jmaredistinct.If there is no possibility for vi to have the color value c1(vi) equal to 0, i.e.,(26)0∉c0vj1+c0vj2+⋯+c0vjmmodm∣j1,j2,…,jmaredistinct,then we call vi 0-avoidable. If all vertices are 0-avoidable, then we say that the initial color value array c0=(c0(v1),c0(v2),…,c0(vn)) isgood. If c0 has k distinct elements under the meaning of modular m, we call c0k-good. The problem to find a k-good initial color value array c0 is called the k-Random WACP underσ+-rule on  Zm. Note that we always assume that n≥m and k≤m when we discuss on the k-Random WACP on Zm.We need to point out that ifn is big enough, the k-Random WACP may have no solution for any k. For example, it is easy to verify that when m=2, n=4, K4 has no k-good initial color value array for any 1≤k≤4; i.e., the k-Random WACP has no solution. In fact, for any 4 integers x1,x2,x3,x4 such that xi=0 or 1, 1≤i≤4, the set(27)x1+x2,x1+x3,x1+x4,x2+x3,x2+x4,x3+x4must have a 2-element subset such that the sum of its elements is equal to 0 under the meaning of modular 2.In the following we will try to find when thek-Random WACP has a solution and how to construct a solution by the help of combinatorial number theory. We need to represent the k-Random WACP by using the terminology in combinatorial number theory as follows:Whether there exists A = ( a 1 , a 2 , … , a n ) , a sequence of elements of Z m of length n such that the number of distinct a i ’s is equal to k , and the sum of any m elements of A is not equal to 0 under the meaning of modular m.It is necessary to introduce Bialostocki Numberf(m,k) from combinatorial number theory. Suppose m, k are positive integers. Denote by f(m,k) the least integer g for which the following holds: If A=(a1,a2,…,ag) is a sequence of elements of Zm of length g such that the number of distinct ai’s is equal to k, then there are m indices i1,…,im belonging to {1,…,g} such that ai1+…+aim=0(modm). It is easy to see that there is a solution to the k-Random WACP for Kn if and only if n<f(m,k).How to calculatef(m,k) is still an open problem in combinatorial number theory. Until now only part of Bialostocki Numbers f(n,k) have been derived. In [27], Gallardo, Grekos, and Pihko proved the following.(1)
Ifm is odd, then f(m,m)=m; if m is even, then f(m,m)=m+1.(2)
Ifm≥5 and 1+m/2<k≤m-1, then f(m,k)=m+2.In [28], Wang proved the following.(1)
Ifk≥3 is odd and m≥max{(k-1)2-4,(k-1)(k+5)/8+2}, then(28)fm,k=2n-k-124-1.(2)
Ifk≥2 is even and m≥max{k(k-2)-4,k(k+2)/8+1}, then(29)fm,k=2m-kk-24-1.Now return to thek-Random WACP. We have the following results.Theorem 19.
Supposem and k are two given positive integers and k≤m. (1)
Whenk=m and m is odd, there is no solution to the k-Random WACP on Zm for Kn.(2)
Whenk=m and m is even, there is a solution to the k-Random WACP on Zm for Kn if and only if n=m, and the initial color value array c0=(0,1,…,m-1) is one solution.(3)
When1+m/2<k<m, there is a solution to the k-Random WACP on Zm for Kn if and only if m≤n≤m+1.(4)
Whenk≥3 is odd and m≥max{(k-1)2-4,(k-1)(k+5)/8+2}, there is a solution to the k-Random WACP on Zm for Kn if and only if m≤n≤2m-(k-1)2/4-2, and the initial color value array(30)c0=0,…,0︸x,1,…,1︸y,2,3,…,k-12,m-k-12,m-k-12+1,…,m-1satisfying1≤x≤m-(k-1)(k+3)/8, 1≤y≤m-(k-1)(k+1)/8, x+y=n-k+2, is one solution.(5)
Whenk≥2 is even and m≥max{k(k-2)-4,k(k+2)/8+1}, there is a solution to the k-Random WACP on Zm for Kn if and only if m≤n≤2m-k(k-2)/4-2, and the initial color value array(31)c0=0,…,0︸x,1,…,1︸y,2,3,…,k-12,m-k-12,m-k-12+1,…,m-1satisfying1≤x≤m-k(k+2)/8, 1≤y≤m-k(k+2)/8, x+y=n-k+2, is one solution.The proof and corresponding solutions constructed can be referred to [27, 28].


## 5. Conclusion

The All-Ones Problem comes from the theory ofσ+-automata, which is related to the graph dynamical system. In this paper, we introduce and study the generalization form of the All-Ones Problem, named “All-Colors Problem.” The “All-Colors Problem” can be divided into Strong-All-Colors Problem and Weak-All-Colors Problem, respectively. We analyze and compute the solutions to these two problems on some interesting classes of graphs. At last we also introduce a new kind of Weak-All-Color Problem, k-Random Weak-All-Colors Problem, which is relevant to both combinatorial number theory and σ+-automata.



---

*Source: 3164692-2019-06-02.xml*