Geodesic
On indices of states in finite dynamic systems of complete graphs orientations
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 176-179 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) $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$.
Keywords: complete graph, evolutionary function, finite dynamic system, graph, index, tournament.
Mots-clés : graph orientation 
@article{PDMA_2019_12_a48,
     author = {A. V. Zharkova},
     title = {On indices of states in finite dynamic systems of complete graphs orientations},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {176--179},
     year = {2019},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a48/}
}
TY  - JOUR
AU  - A. V. Zharkova
TI  - On indices of states in finite dynamic systems of complete graphs orientations
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 176
EP  - 179
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a48/
LA  - ru
ID  - PDMA_2019_12_a48
ER  - 
%0 Journal Article
%A A. V. Zharkova
%T On indices of states in finite dynamic systems of complete graphs orientations
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 176-179
%N 12
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a48/
%G ru
%F PDMA_2019_12_a48
A. V. Zharkova. On indices of states in finite dynamic systems of complete graphs orientations. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 176-179. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a48/

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

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

[3] Salii V. N., “Ob odnom klasse konechnykh dinamicheskikh sistem”, Vestnik Tomskogo gos. un-ta. Prilozhenie, 2005, no. 14, 23–26

[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 # 2009613140. Data postupleniya 22 iyunya 2009 g. Zaregistrirovano v Reestre programm dlya EVM 20 avgusta 2009 g.

[6] Zharkova A. V., “Indeksy v dinamicheskoi sisteme $(B,\delta)$ dvoichnykh vektorov”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 11:3-1 (2011), 116–122

[7] Zharkova A. V., “Indeksy sostoyanii v dinamicheskoi sisteme dvoichnykh vektorov, assotsiirovannykh s orientatsiyami palm”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 16:4 (2016), 475–484 | MR | Zbl