### 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.

#### Keywords

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications