Counting Periodic Points in Parallel Graph Dynamical Systems

Juan A. Aledo, Ali Barzanouni, Ghazaleh Malekbala, Leila Sharifan and Jose C. Valverde

Complexity, 2020, vol. 2020, 1-9

Abstract:

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

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/8503/2020/9708347.pdf (application/pdf)
http://downloads.hindawi.com/journals/8503/2020/9708347.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:complx:9708347

DOI: 10.1155/2020/9708347

Access Statistics for this article

More articles in Complexity from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().