On indices of states in finite dynamic systems of complete graphs orientations

A. V. Zharkova

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 176-179

Résumé

Finite dynamic systems of complete graphs orientations are considered. The states of such a system $(\Gamma_{K_n},\alpha)$, $n>1$, are all possible orientations of a given complete graph $K_n$, and evolutionary function $\alpha$ transforms a given state (tournament) $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. In this paper, the algorithm for calculating indices of states in finite dynamic systems of complete graphs orientations is proposed. Namely, in the considered system $(\Gamma_{K_n},\alpha)$, $n>1$, the index of the state $G\in \Gamma_{K_n}$ is 0 if and only if it hasn't a sink or its indegrees vector $(d^{-}(v_1),d^{-}(v_2),\ldots,d^{-}(v_n))$ is a permutation of numbers $\{0,1,\ldots,n-1\}$. If these conditions for this state $G$ are not met, then its index is $f$, where $f$ is the power of the largest set of the form $\{n-1,n-2,\ldots, n-f\}\subseteq\{d^{-}(v_1),d^{-}(v_2),\ldots,d^{-}(v_n)\}$. The maximal index of the states in the system is found: it is equal to $0$ for $n=2$ and $n-3$ for $n>2$. The corresponding table is given for the finite dynamic systems of orientations of complete graphs with the number of vertices from $2$ to $7$.

Détail

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