On number of inaccessible states in finite dynamic systems of complete graphs orientations

A. V. Zharkova

Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 100-103

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, formulas for calculating the number of inaccessible and the number of accessible states in finite dynamic systems of complete graphs orientations are given. Namely, in the considered system $(\Gamma_{K_n}, \alpha)$, $n>1$, the state ${G}\in \Gamma_{K_n}$ is inaccessible if and only if in this digraph ${G}$ there is no source and there is a sink. In the finite dynamic system $(\Gamma_{K_n}, \alpha)$, $n>1$, the number of inaccessible states is $n \big(2^{{(n-1)(n-2)}/{2}} - (n-1) 2^{{(n-2)(n-3)}/{2}}\big)$ and the number of accessible states is $2^{{n(n-1)}/{2}} - n \big(2^{{(n-1)(n-2)}/{2}} - (n-1) 2^{{(n-2)(n-3)}/{2}}\big)$. The corresponding table is given for the finite dynamic systems of complete graphs orientations with the number of vertices from $2$ to $10$.

Détail

Keywords: accessible state, complete graph, evolutionary function, finite dynamic system, graph, inaccessible state, index, sink, tournament.
Mots-clés : graph orientation, source