Attractors and cyclic states in finite dynamic systems of complete graphs orientations

A. V. Zharkova

Prikladnaâ diskretnaâ matematika, no. 1 (2023), pp. 80-87.

Résumé

Graph models occupy an important place in information security tasks. Finite dynamic systems of complete graphs orientations are considered. States of a dynamic system ($\Gamma_{K_n}$, $\alpha$), $n \geq 1$, are all possible orientations of a given complete graph ${K_n}$, and the evolutionary function transforms the complete graph orientation by reversing all arcs that go into sinks, and there are no other differences between the given and the next digraphs. The cyclic (belonging to attractors) states of the system are characterized, namely, state belongs to an attractor, if and only if it hasn't a sink or its indegrees vector is $(n-1,n-2,\ldots,0)$. A table is given with the number of cyclic and non-cyclic states in the systems of complete graphs orientations with the number of vertices from $1$ to $8$ inclusive. The formation of attractors of the system, their type and length are described, namely, there are attractors of length $1$, each of which is formed by state without sink, and attractors of length $n$, each of which is formed by such states $\overrightarrow{G} \in \Gamma_{K_n}$, in which indegrees vector is $(n-1,n-2,\ldots,0)$, wherein each such attractor represents a circuit, in which each next state is obtained from the previous one as follows: if $\overrightarrow{G}$ has vector of indegrees of its vertices in the order of their enumeration $(d^{-}(v_1),d^{-}(v_2),\ldots,d^{-}(v_n))$, then $\alpha(\overrightarrow{G}) \in \Gamma_{K_n}$ has vector of indegrees of its vertices in the order of their enumeration $(d^{-}(v_1)+1,d^{-}(v_2)+1,\ldots,d^{-}(v_n)+1)$, where the addition is calculated modulo $n$, and only these attractors. Note that in the considered finite dynamic systems the number of attractors of length $n$ is equal to $(n-1)!$ and the number belonging to the attractors states is equal to $n!$. A table is given with the corresponding number of attractors in the systems of complete graphs orientations with the number of vertices from $1$ to $8$ inclusive.

Détail

Keywords: attractor, complete graph, cybersecurity, cyclic state, directed graph, evolutionary function, fault-tolerance, finite dynamic system, graph, information security.

Bibliographie

[1] Barbosa V. C., An Atlas of Edge-Reversal Dynamics, Chapman Hall/CRC, London, 2001, 372 pp. | MR

[2] Colon-Reyes O., Laubenbacher R., and Pareigis B., “Boolean monomial dynamical systems”, Ann. Combinatorics, 8 (2004), 425–439 | DOI | MR

[3] Salii V. N., “On a class of finite dynamic systems”, Vestnik TSU. Prilozheniye, 2005, no. 14, 23–26 (in Russian)

[4] Bogomolov A. M. and Salii V. N., Algebraic Foundations of the Theory of Discrete Systems, Nauka, Fizmatlit, M., 1997, 368 pp. (in Russian) | MR

[5] Vlasova A. V., “Attractors of dynamic systems associated with cycles”, Prikladnaya Diskretnaya Matematika, 2011, no. 2(12), 90–95 (in Russian)

[6] Zharkova A. V., “Attractors in finite dynamic systems of binary vectors associated with palms orientations”, Prikladnaya Diskretnaya Matematika, 2014, no. 3(25), 58–67 (in Russian) | MR