Ulutaş T., Köroğlu M. E.
SYMMETRY, cilt.18, sa.10, ss.1-27, 2026 (Scopus)
-
Yayın Türü:
Makale / Tam Makale
-
Cilt numarası:
18
Sayı:
10
-
Basım Tarihi:
2026
-
Doi Numarası:
10.3390/sym18101658
-
Dergi Adı:
SYMMETRY
-
Derginin Tarandığı İndeksler:
Academic Search Ultimate (EBSCO), Scopus, Materials Science & Engineering Collection (ProQuest), Technology Collection (ProQuest), INSPEC, zbMATH
-
Sayfa Sayıları:
ss.1-27
-
Açık Arşiv Koleksiyonu:
AVESİS Açık Erişim Koleksiyonu
-
Yıldız Teknik Üniversitesi Adresli:
Evet
Özet
Sequential dynamical systems (SDSs) are discrete dynamical systems defined by a graph, a collection of local update functions, and an update order. A central problem in their theory is to determine the maximum number of periodic orbits of a given period that can appear in the phase space of a system on a fixed graph. Extending Defant’s correspondence between period-2 orbits and binary codes to the ternary setting, we recently showed that the maximum number of period-3 orbits of an SDS on the complete graph equals the maximum size of a ternary code with a minimum Hamming distance of at least four. Building on that structural correspondence, the present paper provides a stage-by-stage computational analysis of the associated graph construction, exact search, SDS realization, consistency checking, and candidate-verification procedures. The admissibility graph realizing the extremal quantity as a clique number can be constructed in O(32m−2m) time, and a supplied clique of size k can be processed through the construction, consistency-checking, and orbit-verification stages in O(k2m2) time under the stated assumptions. This is polynomial in the explicit candidate parameters. Substituting k≤3m−1 yields the m-only upper bound O(32m−2m2); this reparameterization does not imply non-polynomial verification in the explicit input size. Determining the extremal value from scratch, however, requires solving a Maximum Clique problem. By the Moon–Moser theorem, an N-vertex graph can have as many as 3N/3 maximal cliques, with N=3m−1 in the present setting; thus an enumeration-based exact strategy may face a doubly exponential family of maximal cliques in m. This general bound is not a prediction of the search tree observed for the tested instances. Since the SDS graph and the corresponding coding graph have vertex sets of equal size, equality of vertex counts alone gives no immediate asymptotic advantage at the level of the presented worst-case search-space bound; it does not imply identical practical difficulty. The SDS formulation is therefore best understood as a structured framework for constructing and checking candidate solutions rather than as a faster exact algorithm. We do not claim a new complexity-class characterization, lower bound for the admissibility-graph family, or general-purpose Maximum Clique algorithm.