RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2018 Issue 11, Pages 106–109 (Mi pdma415)

This article is cited in 2 papers

Applied Theory of Coding, Automata and Graphs

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

A. V. Zharkova

Saratov State University, Saratov

Abstract: 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.

Keywords: attractor, complete graph, evolutionary function, finite dynamic system, graph, graph orientation, tournament.

UDC: 519.1

DOI: 10.17223/2226308X/11/33



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025