Counting Periodic Points in Parallel Graph Dynamical Systems
Let F: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 theo...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/9708347 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832555055319875584 |
|---|---|
| author | Juan A. Aledo Ali Barzanouni Ghazaleh Malekbala Leila Sharifan Jose C. Valverde |
| author_facet | Juan A. Aledo Ali Barzanouni Ghazaleh Malekbala Leila Sharifan Jose C. Valverde |
| author_sort | Juan A. Aledo |
| collection | DOAJ |
| description | Let F: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. |
| format | Article |
| id | doaj-art-70521294f0bb46b4a9eb3e05446365cf |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-70521294f0bb46b4a9eb3e05446365cf2025-02-03T05:49:38ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/97083479708347Counting Periodic Points in Parallel Graph Dynamical SystemsJuan A. Aledo0Ali Barzanouni1Ghazaleh Malekbala2Leila Sharifan3Jose C. Valverde4Department of Mathematics, University of Castilla-La Mancha, Albacete, SpainDepartment of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, IranDepartment of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, IranDepartment of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, IranDepartment of Mathematics, University of Castilla-La Mancha, Albacete, SpainLet F: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.http://dx.doi.org/10.1155/2020/9708347 |
| spellingShingle | Juan A. Aledo Ali Barzanouni Ghazaleh Malekbala Leila Sharifan Jose C. Valverde Counting Periodic Points in Parallel Graph Dynamical Systems Complexity |
| title | Counting Periodic Points in Parallel Graph Dynamical Systems |
| title_full | Counting Periodic Points in Parallel Graph Dynamical Systems |
| title_fullStr | Counting Periodic Points in Parallel Graph Dynamical Systems |
| title_full_unstemmed | Counting Periodic Points in Parallel Graph Dynamical Systems |
| title_short | Counting Periodic Points in Parallel Graph Dynamical Systems |
| title_sort | counting periodic points in parallel graph dynamical systems |
| url | http://dx.doi.org/10.1155/2020/9708347 |
| work_keys_str_mv | AT juanaaledo countingperiodicpointsinparallelgraphdynamicalsystems AT alibarzanouni countingperiodicpointsinparallelgraphdynamicalsystems AT ghazalehmalekbala countingperiodicpointsinparallelgraphdynamicalsystems AT leilasharifan countingperiodicpointsinparallelgraphdynamicalsystems AT josecvalverde countingperiodicpointsinparallelgraphdynamicalsystems |