On attractors in finite dynamic systems of complete graphs orientations

A. V. Zharkova

Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 112-114

Résumé

Finite dynamic systems of complete graphs orientations are considered. The states of such a system $S=(\Gamma_{K_n},\alpha)$, $n>1$, are all possible orientations $G$ of the complete graph $K_n$, and evolutionary function $\alpha$ transforms a given state $G$ by reversing all arcs in $G$ that enter into sinks, and there are no other differences between the given ($G$) and the next ($\alpha(G)$) states. The following criterion for belonging states to attractors in $S$ is given: a state $G$ belongs to an attractor if and only if it hasn't a sink or its indegrees vector is a permutation of numbers $0,1,\dots,n-1$. All attractors in $S$ are the attractors of length $1$, each of which consists of states without sinks, and the attractors of length $n$, each of which consists of states with indegrees vectors being permutations of numbers $0,1,\dots,n-1$. Any such an attractor represents a circuit, for every state $G$ in which if the indegrees vector of $G$ is $(d^-(v_1),d^-(v_2),\dots,d^-(v_n))$, then the indegrees vector of $\alpha(G)$ is $(d^-(v_1)+1,d^-(v_2)+1,\dots,d^-(v_n)+1)$, where the addition is calculated modulo $n$. Note that in system $S$, the number of attractors of length $n$ is equal to $(n-1)!$ and the number of states belonging to them is equal to $n!$.

Détail

Keywords: attractor, complete graph, evolutionary function, finite dynamic system, graph
Mots-clés : graph orientation.