Cycle bases of reduced powers of graphs

Abstract

We define what appears to be a new construction. Given a graph G and a positive integer k, the reduced kth power of G, denoted G^(k), is the configuration space in which k indistinguishable tokens are placed on the vertices of G, so that any vertex can hold up to k tokens. Two configurations are adjacent if one can be transformed to the other by moving a single token along an edge to an adjacent vertex. We present propositions related to the structural properties of reduced graph powers and, most significantly, provide a construction of minimum cycle bases of G^(k).

The minimum cycle basis construction is an interesting combinatorial problem that is also useful in applications involving configuration spaces. For example, if G is the state-transition graph of a Markov chain model of a stochastic automaton, the reduced power G^(k) is the state-transition graph for k identical (but not necessarily independent) automata. We show how the minimum cycle basis construction of G^(k) may be used to confirm that state-dependent coupling of automata does not violate the principle of microscopic reversibility, as required in physical and chemical applications.