Source reversal and chip firing on graphs (Q1575961)

An orientation of a connected finite undirected graph \(G=(V,E)\) is a directed graph obtained by assigning an arbitary direction to every edge of \(G\). Let \({\mathcal O}(G)\) be the set of all orientations of \(G\). For \(D\in{\mathcal O}(G)\), define \(\Phi(D)\) as the orientation obtained from \(D\) by reversing the directions of all arcs going outside sources (vertices with indegree zero) in parallel. The set \({\mathcal O}(G)\) together with the mapping \(\Phi\) forms a discrete dynamical system, called source reversal, which is studied. For instance, the authors characterize the gardens of eden, i.e., orientations \(D\) such that there does not exist \(D'\in{\mathcal O}(G)\) with \(\Phi(D')=D\). They also prove that if \(D\) is an acyclic orientation, then \(\Phi^{{|V|-1 \choose 2}}(D)\) is stationary. Moreover, a wide class of graphs all their orientations have no period greater than \(|V|\) is given. The source reversal system has relations with the so-called parallel chip firing with \(|E|\) chips. A configuration of \(G\) is a distributions of \(|E|\) chips on the vertices of \(G\). For a configuration \(C\), let \(\Psi(C)\) be the configuration obtained in the following way: each vertex with at least as many chips as its degree sends one chip to each of its neighbors. Let \({\mathcal C}_{|E|}(G)\) be the set of configurations of \(G\). Each orientation \(D\) of \(G\) gives the configuration \(F(D)\) which consists in putting in each vertex \(x\) of \(G\) a number of chips equal to the outdegree of \(x\) in \(D\). Some properties of the mapping \(F\colon{\mathcal O}(G)\rightarrow{\mathcal C}_{|E|}(G)\) are established. For instance, the configurations of \(F({\mathcal O}(G))\) are characterized; in particular every periodic nonstationary configuration belongs to \(F({\mathcal O}(G))\). Then, periods in source reversal coincide with periods in chip firing with \(|E|\) chips and the above-mentioned class gives a class of graphs with no periods greater than \(|V|\) under chip firing.