On the number of attractors in finite dynamic systems of complete graphs orientations

A. V. Zharkova

Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 106-109

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) $\vec G$ by reversing all arcs in $\vec G$ that enter into sinks, and there are no other differences between the given $\vec G$ and the next $\alpha(\vec G)$ states. In this paper, the number of attractors in finite dynamic systems of complete graphs orientations is counted. Namely, in the considered system $(\Gamma_{K_n},\alpha)$, $n>1$, the total number of attractors (basins) is $2^{(n-1)(n-2)/2}(2^{n-1}-n)+(n-1)!$, wherein the number of attractors of length $1$ is $2^{(n-1)(n-2)/2}(2^{n-1}-n)$ and of length $n$ is $(n-1)!$. The corresponding tables are given for the finite dynamic systems of orientations of complete graphs with the number of vertices from two to ten inclusive.

Détail

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