The finite dynamic system of all possible orientations of a given graph with all accessible states and with inaccesible states

A. V. Zharkova

Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 105-107

Résumé

The finite dynamic systems $(\Gamma_G, \alpha)$ is considered, the states of which are all possible orientations of a given graph $G$, and the evolutionary function $\alpha$ transforms a given state $\overrightarrow{G}$ by reversing all arcs in $\overrightarrow{G}$ that enter into sinks, and there are no other differences between the given $\overrightarrow{G}$ and the next $\alpha(\overrightarrow{G})$ states. We characterize the systems in which all states are accessible and in which there are inaccessible states. Namely, in a finite dynamic system $(\Gamma_G,\alpha)$ all states are accessible if and only if the (connected) components in the graph $G$ are complete graphs with $n$ vertices for $1\leq n\leq3$ and only they. Otherwise, the system under consideration has inaccessible states. The number of graphs forming systems with all accessible states is counted. Namely, the number of graphs $G$ with $n$ vertices that form finite dynamic systems $(\Gamma_G,\alpha)$, all states of which are accessible, is equal to $1+\left\lfloor{n}/{2}\right\rfloor+\left\lfloor{n}/{3}\right\rfloor+\sum\limits_{i=1}^{\left\lfloor (n-3)/{2}\right\rfloor}\left\lfloor(n-2i)/{3}\right\rfloor$. The table is given with the number of graphs with the number of vertices from 1 to 12, forming systems with all accessible states and with inaccessible states.

Détail

Keywords: accessible state, directed graph, evolutionary function, finite dynamic system, fault-tolerance, graph, inaccessible state.