# Counting Periodic Points in Parallel Graph Dynamical Systems

Authors: Juan A. Aledo; Ali Barzanouni; Ghazaleh Malekbala; Leila Sharifan; Jose C. Valverde
Journal: Complexity
 (2020)

---

## Abstract

LetF:0,1n⟶0,1n be a parallel dynamical system over an undirected graph with a Boolean maxterm or minterm function as a global evolution operator. It is well known that every periodic point has at most two periods. Actually, periodic points of different periods cannot coexist, and a fixed point theorem is also known. In addition, an upper bound for the number of periodic points of F has been given. In this paper, we complete the study, solving the minimum number of periodic points’ problem for this kind of dynamical systems which has been usually considered from the point of view of complexity. In order to do this, we use methods based on the notions of minimal dominating sets and maximal independent sets in graphs, respectively. More specifically, we find a lower bound for the number of fixed points and a lower bound for the number of 2-periodic points of F. In addition, we provide a formula that allows us to calculate the exact number of fixed points. Furthermore, we provide some conditions under which these lower bounds are attained, thus generalizing the fixed-point theorem and the 2-period theorem for these systems.


---

## Body

## 1. Introduction

Dynamical systems have a long and brilliant history of applications in biological networks [1], epidemic networks [2], social networks [3], and engineering control systems [4]. In this paper, we deal with a particular class of finite dynamical systems, named deterministic Boolean networks [5, 6]. A deterministic Boolean network is a time-discrete dynamical system F:0,1n⟶0,1n whose evolution operator is also a Boolean function. These networks were introduced by Kauffman [7] and also studied in works like [8–11] as models of genes activity and interactions.Besides the applications of Boolean networks in biological and social systems [12], these networks have been used in other branches of science for modeling problems in different fields such as computer science [13, 14], chemistry [15, 16], mathematics [17, 18], and physics [19, 20]. In fact, due to their versatility, Boolean networks have become a profusely studied topic [5, 6, 21–26] in the last two decades.Boolean networks can be represented by means of graphs. Specifically, associated with a (simple undirected) graphG=V,E with vertex set V=1,…,n and a Boolean function f:0,1n⟶0,1, we can define a homogeneous dynamical system, denoted by F:(1)F:0,1n⟶0,1n,Fx1,…,xn=y1,…,yn,such that each yi is given by the function fi which is the restriction of the global function f to the state of the entity i and its neighbors. The graph G is called the dependency graph of F. When all the entities are updated in a synchronous manner, the system is called a parallel dynamical system (PDS) [27–34], while if all the entities are updated in an asynchronous way, the system is called a sequential dynamical system [5, 6, 24, 35, 36]. When the function f is a maxterm (resp., a minterm), the system is called MAX−PDS (resp., MIN−PDS), in the parallel case, while in the sequential case, it is named MAX-SDS (resp., MIN-SDS). Here, by maxterm (resp., minterm), we mean fx1,…,xn=z1∨⋯∨znresp.,fx1,…,xn=z1∧⋯∧zn, where zi=xi or zi=xi′.Following the notations of [33], we shall denote by W⊆V(resp., W′⊆V) the set of vertices in V such that the corresponding variables in f appear in a direct (resp., complemented) form. Moreover, for each i∈V and Q⊆V, we define(2)AGi=j:i,j∈E,AGi¯=AGi∪i,AGQ=∪i∈QAGi,AGQ¯=AGQ∪Q.Previous studies in deterministic Boolean (finite) networks (also known asBoolean finite dynamical systems) show that the relationship between the structure of the network and its dynamics is a key issue. In this sense, some authors have set out the dynamical problem of finding fixed points and periodic points (see, for instance, [26, 36–45]). From the point of view of complexity, the problem of finding fixed points (or, more generally, periodic points) of these systems is NP-hard [46, 47]. Related to the problem of counting periodic points, other problems such as the maximum number problem and the minimum number problem are usually considered. In the literature, one can find some works on the study of the maximum number of fixed points of particular classes of Boolean finite dynamical systems (see [37–39]). In particular, in [38, 39], the authors established a relationship between the maximum number of fixed points in a special class of PDS and the maximum number of maximal independent sets. In this paper, we use such maximal independent sets to establish the minimum number of 2-periodic points in homogeneous PDS induced by a maxterm or minterm. Regarding the minimum number of fixed points’ problem, in the recent work [48], the authors studied its complexity and established that finding a Boolean network having at least k fixed points is in P or complete for NP, NP#P, or NEXPTIME, depending on the input.In particular, for homogeneous PDS over a maxterm (or minterm) Boolean function, a crucial result in [33] proves that if F is a MAX−PDS (or MIN−PDS) over a dependency graph G, then all the periodic points of this system are fixed points, or all of them are 2-periodic points. Actually, the authors found necessary and sufficient conditions under which all the periodic points of a MAX−PDS (resp., a MIN−PDS) are fixed points or all of them are 2-periodic points. When all the periodic points of the system are fixed points, we simply say that F is a fixed point system and when all of them are 2-periodic points, we say F is a 2-periodic point system. In addition, a criterion was given to check if the system has a unique fixed point.Later, in [34], the authors found a characterization of MAX−PDS (resp., a MIN−PDS) to have a unique 2-periodic orbit. Moreover, an upper bound for the number of fixed points and the number of 2-periodic points of such systems were also obtained in [34], thus solving the maximum number problems in this context.In this work, our main goal is to provide lower bounds for the number of fixed points and the number of periodic points of an arbitraryMAX−PDS (and MIN−PDS), i.e., to solve the minimum number problems. Besides, we provide formulae for counting (exactly) such points for PDS over different particular classes of graphs. The results are shown here only for MAX−PDS, since they can be easily translated to the case of MIN−PDS by duality. Likewise, the results on fixed points are also valid for MAX-SDS (and MIN-SDS) since, as well known, fixed points of an SDS are the same as the corresponding PDS.This paper is organized as follows. Section2 is devoted to counting fixed points and establishing the minimum number of them. For an arbitrary PDS on a maxterm, namely, F, over a dependency graph G=V,E, we induce a bipartite graph BF on a vertex set V1∪˙V2 (see Definition 2) and define the notion of dominating sets of V2 in BF (see Definition 1). Next, we provide a characterization of the fixed points of F in terms of such dominating sets (see Theorem 2). The bijective correspondence between the fixed points and dominating sets allows us to reformulate the known theorems on the existence and uniqueness of fixed points in terms of such dominating sets (see Theorem 3). Such a correspondence also allows us to get the same upper bound for number of fixed points as in [34]. Moreover, the new method to obtain this upper bound provides a characterization to attain this maximum number of fixed points (see Corollary 1). Finally, we consider minimal dominating sets and provide a lower (combinatorial) bound for the number of fixed points of F (see Theorem 4). Furthermore, we are able to get a characterization for MAX−PDS to have such minimum number of fixed points in Theorem 5, thus solving the minimum number of fixed-point problems for this kind of PDS. Note that Theorem 5 can be considered as a generalization of the fixed-point theorem ([33], Theorem 9). In this section, we also provide a formula to easily count (exactly) the fixed points (see Theorem 6). In Section 3, we assume that F is a 2-periodic point MAX−PDS and study the number of its 2-periodic points. In this case, we use a counting method based on the notion of maximal independent sets of a graph and the corresponding independence number. First, we provide a lower bound for the number of 2-periodic points in the case of the maxterm NAND (see Theorem 7). Moreover, in such a case, we provide a sufficient condition to attain this lower bound in Corollary 3. As a consequence, we give a simple formula for counting (exactly) the 2-periodic points when G is a t-partite graph or a n−2 regular graph (see Corollary 3). Finally, by combining the previous results, we give a lower combinatorial bound for the number of 2-periodic points of a MAX−PDS (see Theorem 8). We also provide an example to prove that this bound is the best possible one, i.e., it is the minimum number of 2-periodic points. We conclude the paper giving some conclusions and future research directions in Section 4.


## 2. Minimum Number of Fixed Points in PDS

First, we recall a crucial theorem for characterizingMAX−PDS which are fixed-point systems and for determining when a MAX−PDS has a unique fixed point.Theorem 1 (see [33], Theorems 3 and 9).
LetF be a MAX−PDS over a dependency graph G=V,E, G1,…,Gp be the connected components of G\W′, and(3)W1′=i∈W′:∃!1≤j≤p,suchthati∈AGVGj,where VGj is the set of vertices of Gj. Then,(1)
F is a fixed point system if, and only if, W∩AGi≠∅ for all i∈W′.(2)
IfF is a fixed point system, then F has a unique fixed point if and only if for all 1≤j≤p, AGVGj∩W1′≠∅. In such a case, the unique fixed point of the system is the one with all the state values equal to 1.Remark 1.
(see [33], Section 3). We also know that if x^=x1,…,xn is a fixed point, then(fp1) All the variables associated with the vertices inW′ are activated(fp2) For each1≤i≤p, all the variables associated with the vertices in Gi are activated, or all of them are deactivated(fp3) Moreover, ifGj1,Gj2,…,Gjl are the connected components adjacent to a vertex j∈W′, then not all (the variables associated with the vertices in) these components can be deactivated simultaneously; otherwise, the value of xj would change from 1 to 0 in the following iteration.
From this characterization of fixed points, in Theorem 1 of [34], it was stated that the number of fixed points of a fixed-point system MAX−PDS over a connected graph with MAX≠OR is upper bounded by 2p−1. For the well-known case, when MAX=OR, the number of fixed points is equal to 2.
Taking these results into account, we then provide a novel combinatorial characterization of the fixed points of aMAX−PDS. In order to do this, we need some notions of graph theory.Definition 1.
LetB be a bipartite graph whose disjoint sets of vertices are V1 and V2 (i.e., V1∪˙V2=VB and each edge of B has an endpoint in V1 and an endpoint in V2). Then, we say that S⊆V1 is a dominating set ofV2 in B if every vertex in V2 is adjacent to at least one in S. In this situation, we define(4)ηB=minS:S⊆V1is a dominating set ofV2inB.
Note that Definition1 is an adaptation of the usual notion of dominating set in graph theory to bipartite graphs.
Next, for eachMAX−PDS over a dependency graph G, we induce a bipartite graph B.Definition 2.
LetF be a MAX−PDS over a dependency graph G=V,E with ∅≠W′⊊V, and let G1,…,Gp be the connected components of G\W′. Associated with this MAX−PDS, we define a bipartite graph BF in which VBF=V1∪˙V2 as(i)
V1=1¯,…,p¯. Intuitively, we collapse the connected component Gi into a single vertex i¯ for i=1,…,p.(ii)
V2=W′.(iii)
The edge set ofBF is defined as(5)i¯,j∈EBF⟺∃k∈Giadjacent toj.Example 1.
Assume thatG=V,E is the graph of Figure 1.
Let us take(6)fx1,x2,x3,x4,x5,x6,x7,x8,x9=x1∨x2∨x3∨x4∨x5∨x6∨x7′∨x8′∨x9′.
Then,W′=7,8,9 and G\W′ has 4 connected components: G1=1,2, which we collapse into the vertex 1¯; G2=3, which we collapse into the vertex 2¯; G3=4, which we collapse into the vertex 3¯; and G4=5,6, which we collapse into the vertex 4¯. Then, bearing in mind the edges between the vertices in W′ and those in the components Gi, the bipartite graph BF becomes as shown in Figure 2:
As a key point for our study, we then show that there is a bijective correspondence between the dominating sets ofV2 in BF and the fixed points in the MAX−PDS system.Figure 1
GraphG.Figure 2
GraphBF.Theorem 2.
LetF be a MAX−PDS system over a dependency graph G=V,E with W′≠∅, G1,…,Gp be the connected components of G\W′ and BF be the associated bipartite graph. Then, there exists a bijective correspondence between the dominating sets of V2 in BF and the fixed points of the system.In particular(7)FixF=S⊆V1:SisadominatingsetofV2inBF,where FixF is the set of fixed points of the system.Proof.
LetΣ be the set of dominating sets of V2 in BF and let us consider the map Ψ:Σ⟶FixF defined as follows: given S∈Σ, we take ΨS as the point x=x1,…,xn∈0,1n such that(Ψ1) All the variables associated with the vertices in W′ are activated(Ψ2) For each i, 1≤i≤p, if i¯∈S, then all the variables associated with the vertices in Gi are activated; otherwise, all the variables associated with the vertices in Gi are deactivated
Observe thatΨS is a fixed point of the system (see Remark 1), i.e., Ψ is well-defined. Moreover Ψ is injective since ΨS1≠ΨS2 for S1,S2∈Σ with S1≠S2. Finally, given a fixed point x∈FixF and taking into account (fp1), (fp2), and (fp3) in Remark 1, the subset S of V1, whose elements are the vertices i¯ such that the vertices of Gi are activated in x, is a dominating set of V2 verifying that ΨS=x, i.e., Ψ is surjective.With all of these, we can rewrite Theorem1 to check if a MAX−PDS is a fixed-point system and if it has a unique fixed point in terms of the bipartite graph BF.Theorem 3.
LetF be a MAX−PDS system over a dependency graph G=V,E with ∅≠W′⊊V, and BF, the associated bipartite graph. Then,(i)
F is a fixed point system if, and only if, V1 is a dominating set of V2 in BF(ii)
F has a unique fixed point if, and only if, V1 is the unique dominating set of V2 in BFProof.
(i)
By Theorem1, F is a fixed point system if and only if W∩AGj≠∅ for all j∈W′. But this occurs, if and only if, for all j∈W′, there exists i, 1≤i≤p such that j∈AGVGi, which is equivalent to say that V1 is a dominating set of V2 in BF. Therefore, the conclusion follows.(ii)
By Theorem2, every fixed point corresponds to a dominating set. Thus, we have a unique fixed point if, and only if, we have a unique dominating set in G. This occurs if, and only if, V1 is the unique dominating set.LetF be a MAX−PDS over a dependency graph G=V,E in which ∅≠W′⊊V. In Theorem 1 of [34], it is proved that the maximum number of fixed points for this system is 2p−1, where p is the number of connected components of G\W′. In the next corollary, we find a necessary and sufficient condition for achieving this upper bound. Recall that a bipartite graph with V=V1∪˙V2 is said to be a complete bipartite graph, if each node of V1 is adjacent to all the nodes in V2.Corollary 1.
LetF be a MAX−PDS system over a dependency graph G=V,E with ∅≠W′⊊V, G1,…,Gp be the connected components of G\W′, and BF be the associated bipartite graph. Then, FixF=2p−1 if, and only if, BF is a complete bipartite graph.Proof.
It is enough to note that, by Theorem2, FixF is maximum if, and only if, each arbitrary nonempty subset of V1 is a dominating set of V2 in BF which is equivalent to say that BF is a complete bipartite graph.Let us consider the order relation onΣ defined by(8)S1≤S2⟺S1⊆S2,S1,S2∈Σ.Regarding this order, a dominating setS1 is said to be minimal if there is not another dominating set S2 such that S2⊈S1.Note that ifS a dominating set of V2 and T⊆V1 is such that S⊆T, then T is also a dominating set.With all of these, we can provide a lower bound for the number of fixed points in a PDS as follows.Theorem 4.
LetF be a MAX−PDS system over a dependency graph G=V,E with ∅≠W′⊊V, G1,…,Gp be the connected components of G\W′, and BF be the associated bipartite graph. Then, the number of fixed points is, at least, 2p−ηBF. That is,(9)FixF≥2p−ηBF.Proof.
GivenS a dominating set such that S=ηBF, we know that S∪T is also a dominating set of V2 for each T⊆V1\S.
SinceV1\S=p−ηBF, the possibilities of choosing T⊆V1\S are 2p−ηBF. Therefore, we have at least such number of dominating sets and, as a consequence of Theorem 2, at least such number of fixed points.Once we know the lower bound for the number of fixed points, we can establish a minimum number of fixed-point theorem, thus generalizing the fixed-point theorem given for PDS in [33], as follows.Theorem 5 (minimum number of fixed-point theorem).
LetF be a MAX−PDS system over a dependency graph G=V,E with ∅≠W′⊊V, G1,…,Gp be the connected components of G\W′, and BF be the associated bipartite graph. Then, the number of fixed points is minimum if, and only if, there exists a unique minimal dominating set of V2 in BF. In such a case, this minimum number of fixed points is given by(10)FixF=2p−ηBF.Proof.
Observe that the proof consists in getting the equality in the formula of Theorem4 under the assumption of the existence of a unique minimal dominating set. Certainly, the equality follows under this assumption by taking into account that, if S is the unique minimal dominating set of V2, then S=ηBF and every other dominating set of V2 is of the form S∪T for T⊆V1S.
Conversely, ifS1andS2 are two different minimal dominating sets of V2 in BF and S1=ηBF, then S2∉S1∪T;T⊆V1\S1. Thus, F would have at least 2p−ηBF+1 fixed points.Example 2.
LetG be the graph of Figure 3.
Assume that(11)fx1,x2,x3,x4,x5,x6,x7=x1∨x2∨x3∨x4∨x5∨x6′∨x7′.
Then, by definition,BF is the graph of Figure 4.
It is easy to see that1¯ is the unique minimal dominating set of 6,7 in BF, ηBF=1, and G\W′ has 3 connected components. By Theorem 4, F has 4 fixed points which are (see Theorem 3)(12)FixF=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1.
Let us takeM the set of minimal dominating sets of V2 and(13)S¯=∪S∈MS,and then the union of all the minimal dominating sets of V2.
As stated in Theorem4, if M=1, we have that(14)FixF=2p−ηBF.
In this line, we are able to provide a formula for counting (exactly) the fixed points of the system.Figure 3
GraphG.Figure 4
GraphBF.Theorem 6.
LetF be a MAX−PDS system over a dependency graph G=V,E with ∅≠W′⊊V, G1,…,Gp be the connected components of G\W′, and BF be the associated bipartite graph. Let M=S1,…,Sq be the set of minimal dominating sets of V2 in BF, S¯=∪j=1qSj, and(15)Ω=S⊆V1:Sj⊆S⊆S¯for somej1≤j≤q.
Then,(16)FixF=Ω2p−S¯.Proof.
The equality follows from Theorem3 taking into account that if S is a dominating set of V2, S∪T is also a dominating set of V2 for all T⊆V1\S.
As a consequence, we have the following result whenq≥2:Corollary 2.
LetF be a MAX−PDS system over a dependency graph G=V,E with ∅≠W′⊊V, G1,…,Gp be the connected components of GW′, and BF be the associated bipartite graph. Let M=S1,…,Sq (q≥2) be the set of minimal dominating sets of V2 in BF, S¯=∪j=1qSj, and assume that S¯\Sj=1 for all j, 1≤j≤q. Then,(17)FixF=q+12p−S¯.Remark 2.
LetF be an arbitrary MIN−PDS over a dependency graph G=V,E. Then, all the results of this section can be restated for F by duality.


## 3. Minimum Number of 2-Periodic Points in PDS

In this section, we provide a lower bound for the number of 2-periodic points of aMAX−PDS when it is a 2-periodic point system. To do this, we will use Proposition 3 in [34], where the number of 2-periodic orbits of a NAND-PDS is computed:Proposition 1 (see [34], Proposition 3).
LetF be the NAND−PDS over the dependency graph G=V,E and PV be the power set of V. Then, the number of 2-periodic points of this system is Θ, where(18)Θ=AGQ¯:Q∈PV.Specifically, in this proposition, it is proved that(19)x=x1,…,xn∈Per2F,if and only ifj:xj=1∈Θ,where Per2F is the set of 2-periodic points of the system.GivenG=V,E, we say that S⊂V is an independent set of G if i,j∉E for whichever i,j∈S. Furthermore, S is said to be a maximal independent set if S∪k is not independent for all k∈V\S . The independence number of G, αG, is then defined as(20)αG=maxS:S⊆VGis an independent set.In the next result, we give a lower bound for the number of 2-periodic points of aNAND−PDS.Theorem 7.
LetF be the NAND−PDS over a dependency graph G=V,E. Then,(21)Per2F≥2αG.Proof.
GivenF a NAND−PDS over G, we know by Proposition 1 that Per2F=Θ.
LetS be a maximal independent set of G with S=αG. One can easily see that for any two distinct subsets Q1 and Q2 of S, AGQ1¯≠AGQ2¯. Therefore, Θ has, at least, 2αG elements.As a consequence, we have the following.Corollary 3.
LetF be the NAND−PDS over the dependency graph G=V,E, and let S be a maximal independent set of G such that S=αG and AGi¯=V for each i∈V\S. Then, Θ=2αG.Proof.
As shown in the proof of Theorem7, for every two different subsets of S, we have two different 2-periodic points.
On the other hand, for anyQ⊄S, there is i∈Q such that i∈V\S. Hence, V=AGi⊂AGQ. As S is a maximal independent set, AGS=V=AGQ. Thus, only distinct subsets of S generate different periodic points, and the equality holds.In particular, ifG is a complete graph, then it satisfies the conditions of the Corollary, being αG=1, and the number of periodic points of the corresponding NAND−PDS coincides with 2αG=2 ([34], Proposition 1), i.e., the bound provided in Theorem 7 is attained.This situation in Corollary3 also happens, for example, when G is a star graph where the center is the unique point outside the maximal independent set. Thus, the number of 2-periodic points is 2n−1, which matches with the lower bound (see [34], Example 2).Let us present another example.Example 3.
LetG be the graph of Figure 5.
One can easily see that1,2,3 is a maximal independent set in G and αG=3. Moreover, AG4¯=AG5¯=AG6¯=1,2,3,4,5,6. Then, from Corollary 3, we have that Θ=23=8. Actually, Θ=AGQ¯:Q⊆1,2,3.
Next, we compute the number of 2-periodic points of aNAND−PDS over a complete t-partite graph. Recall that the complete t-partite graph G=Kn1,…,nt is a graph whose set of nodes V is the union of pairwise disjoint subsets V1,…,Vt, with Vi=ni, and such that each vertex in Vi is adjacent to all the vertices in V\Vi, i=1,…,t.Figure 5
GraphG.Corollary 4.
LetF be the NAND−PDS over the complete t-partite graph G=Kn1,…,nt. Then,(22)Per2F=∑i=1t2ni−2t−1.
In particular, ifG is the n−2−regular graph, then Per2F=n+2.Proof.
LetG=Kn1,…,nt be the complete t−partite graph on the vertex set V=V1∪˙⋯∪˙Vt. For any ∅≠Q⊆V, two situations are possible:(i)
IfQ⊆Vi for some 1≤i≤t, then AGQ¯=Q∪V\Vi(ii)
IfQ is not contained in Vi for any 1≤i≤t, then AGQ¯=V
Taking also into account thatAG∅¯=∅, we conclude that(23)Θ=V,∅∪AGQ¯:∅≠Q⊊Vi,1≤i≤t,and so(24)Per2F=Θ=2+∑i=1t2ni−2t.
It is easy to check that ifG is n−2−regular, then n is even and G is a complete n/2-partite graph in which every Vi has exactly 2elements (specifically each Vi consists in a pair of nonadjacent vertices). Therefore,(25)Per2F=2+n222−2n2=n+2.Given an arbitrary2−periodic point system MAX−PDS over a dependency graph G=V,E, we are able to obtain a lower bound for Per2F by using Theorems 4 and 7. We will assume that both W and W′ are nonempty sets since the particular cases W=∅ and W′=∅ have been already analyzed in detail.ConsiderW′ as the disjoint union of WD′ and WC′, where(26)WD′=i∈W′:AGi∩W≠∅,WC′=i∈W′:AGi∩W=∅.The restriction of the system to the vertex setW∪WD′, FW∪WD′, is a fixed-point MAX−PDS over the induced subgraph GD of G whose vertex set is W∪WD′ (see [34], Section 3). We also know that the restriction of F to WC′, FWC′, is a 2−periodic point system over the induced subgraph GC of G whose vertex set is WC′.Letx=x1,…,xn be an arbitrary point of 0,1n. Without loss of generality, let us assume that x1,…,xm are the variables associated with the vertices in W∪WD′ and xm+1,…,xn those associated with the vertices in WC′.Observe that ifx1,…,xm is a fixed point of FW∪WD′ and xm+1,…,xn is a 2−periodic point of FWC′, then x is a 2−periodic point of F. In this situation, the variables associated with the vertices in WD′ are fixed to 1, and so they do not affect the updating of the variables associated with vertices in WC′ anymore (see [34], Section 3, for more details).Therefore,(27)Per2F≥Per2FWC′×FixFW∪WD′.In fact, inequality (27) may be strict, as shown in the following example.Example 4.
LetG be the graph of Figure 6.
Assume thatF is the homogeneous MAX−PDS over G whose evolution operator is demaxterm(28)fx1,x2,x3,x4,x5=x1∨x2∨x3′∨x4′∨x5′.
Then, it can be easily checked thatx=0,0,1,1,0 is a 2−periodic point of F (Fx=0,0,0,1,1), but 0,0,1, associated with the vertices 1,2, and 4, is not a fixed point of FGD (FGD0,0,1=0,0,0). Hence, for this system, inequality (27) is strict.
By combining Theorems4 and 7, we have the following result:Figure 6
GraphG.Theorem 8.
LetF be an arbitrary MAX−PDS over a dependency graph G with ∅≠W′⊊V. If F is a 2−periodic point system, then(29)Per2F≥2p−ηBFGD2αGC,where p is the number of connected components of G\W′.We next give an example in which the number of2−periodic points is exactly the same as the lower bound in Theorem 8.Example 5.
Consider the graphG of Figure 7.
If we definef as(30)fx1,x2,x3,x4,x5=x1∨x2∨x3′∨x4′∨x5′,and F is the corresponding homogeneous MAX−PDS, then we have(31)W=1,2,WD′=3,4,WC′=5.
The two connected components ofG\W′=G\WD′∪WC′ consist of the isolated vertices 1 and 2, respectively. Let GD be the induced subgraph of G on the vertex set W∪WD′=1,2∪3,4. For the corresponding bipartite graph BFGD, we have(32)VBFGD=1¯,2¯∪˙3,4,EBFGD=1¯,3,1¯,4∪2¯,3.
It is clear that1¯ is the unique minimal dominating set of V2=3,4 in BFGD. Thus, by Theorem 3, a point x=x1,x2,x3,x4,x5 is a fixed point of FGD if and only if x1=x3=x4=1, and the number of fixed points of FGD is 22−1. Finally, note that GC, the induced subgraph on the vertex set WC′, is an isolated vertex. So, Per2FGC=1,0 and Per2FGC=2αGC=2.
In the following, for eachj≥0, we denote by x1j,…,x5j the point Fjx where x=x10,…,x50.
Assume thatx=x10,x20,x30,x40,x50∈Per2F. Then, by the same discussion before ([34], Theorem 5), x30=x40=1 (so, for each j≥0,x3j=x4j=1) and x50=0 or 1.
We shall show thatx10,x20,x30,x40 is a fixed point of FGD. Actually, if it is not the case, then x10=0 and so, x=0,x20,1,1,1 or x=0,x20,1,1,0. Hence, looking to f4=x1∨x4′∨x5′ we have that x41=0 or x42=0 which is a contradiction. Thus, x10,x20,x30,x40 is a fixed point of FGD.
Therefore, a pointx=x1,x2,x3,x4,x5 is a 2−periodic point of F if, and only if, x1,x2,x3,x4 is a fixed point of FGD and x5 is a 2−periodic point of FGC. In particular,(33)Per2F=FixFGD×Per2FGC=2m−ηDFGD2αGC=22−1×2=22.
Specifically, in our case,Per2F=1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0.Figure 7
GraphG.Remark 3.
LetF be an arbitrary MIN−PDS over a dependency graph G=V,E. Then, all the results of this section can restated for F by duality. Moreover, since the fixed points of a PDS coincide with the ones of any SDS with the same dependency graph and local functions, whichever the update order is, the results obtained in this section are also valid for the case of sequential dynamical systems of the form MAX-SDS and MIN-SDS.


## 4. Conclusions and Future Research Directions

In this paper, we have shown that the problem of counting the fixed points of a homogeneousMAX−PDS can be transformed into the problem of counting minimal dominating sets of an ad hoc bipartite graph constructed from the dependency graph of the system. The method used here has two advantages: first, we can get the results in previous works on the number of fixed points by means of more simple conditions in terms of minimal dominating sets; second, using this new approach, we have been able to provide a lower bound for the number of fixed points of an arbitrary MAX−PDS and to generalize the fixed-point theorem stated in [33] with a minimum number of fixed point theorem; even more, we have also provided a formula to calculate the exact number of such fixed points. Of course, the results are also applicable to any MIN-PDS by duality. Moreover, since the fixed points of a PDS coincide with the ones of any SDS with the same dependency graph and local functions, whichever the update order is, the results on fixed points obtained are also valid for the case of sequential dynamical systems of the form MAX-SDS and MIN-SDS.In addition, we have got a lower bound for the number of2−periodic points of an arbitrary NAND−PDS and, in general, of any MAX−PDS, in terms of the independence number of the dependency graph. Since the independence number is known for many classes of graphs (e.g., complete, path, cycle, and complete k-partite graphs), this method can be useful in many cases. By duality, such lower bounds are also valid to any NOR-PDS and any MIN-PDS, respectively.Our results open some future research directions to be discovered. Actually, we think that, using ideas like the ones in this paper, periodic points ofMAX−PDS (resp., MIN−PDS) over directed graphs [27] could be better analyzed. The techniques employed here could be also interesting to extend this study to sequential dynamical systems, i.e., to those systems where the entities are updated asynchronously.



---

*Source: 9708347-2020-09-14.xml*