Geodesic
On the number of attractors in finite dynamic systems of complete graphs orientations
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 106-109 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, tournament.
Mots-clés : graph orientation 
@article{PDMA_2018_11_a32,
     author = {A. V. Zharkova},
     title = {On the number of attractors in finite dynamic systems of complete graphs orientations},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {106--109},
     year = {2018},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a32/}
}
TY  - JOUR
AU  - A. V. Zharkova
TI  - On the number of attractors in finite dynamic systems of complete graphs orientations
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 106
EP  - 109
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a32/
LA  - ru
ID  - PDMA_2018_11_a32
ER  - 
%0 Journal Article
%A A. V. Zharkova
%T On the number of attractors in finite dynamic systems of complete graphs orientations
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 106-109
%N 11
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a32/
%G ru
%F PDMA_2018_11_a32
A. V. Zharkova. On the number of attractors in finite dynamic systems of complete graphs orientations. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 106-109. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a32/

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

[2] Salii V. N., “Ob odnom klasse konechnykh dinamicheskikh sistem”, Vestnik Tomskogo gosudarstvetherennogo universiteta. Prilozhenie, 2005, no. 14, 23–26

[3] Barbosa V. C., An Atlas of Edge-Reversal Dynamics, Chapman/CRC, London, 2001 | MR | Zbl

[4] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, Fizmatlit, M., 1997 | MR

[5] Vlasova A. V., Issledovanie evolyutsionnykh parametrov v dinamicheskikh sistemakh dvoichnykh vektorov, Svidetelstvo o gosudarstvennoi registratsii programmy dlya EVM No 2009614409, vydannoe Rospatentom. Zayavka No 2009613140. Data postupleniya 22 iyunya 2009 g. Zaregistrirovano v Reestre programm dlya EVM 20 avgusta 2009 g.

[6] Zharkova A. V., “Attraktory v konechnykh dinamicheskikh sistemakh dvoichnykh vektorov, assotsiirovannykh s orientatsiyami palm”, Prikladnaya diskretnaya matematika, 2014, no. 3(25), 58–67 | MR

[7] Zharkova A. V., “Ob attraktorakh v konechnykh dinamicheskikh sistemakh orientatsii polnykh grafov”, Prikladnaya diskretnaya matematika. Prilozhenie, 2016, no. 9, 112–114