#### Document Type

Article

#### Publication Date

11-26-2016

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

#### Journal Title

Ars Mathematica Contemporanea

#### Volume

12

#### Issue

1

#### Recommended Citation

Hammack, Richard H. and Smith, Gregory D., "Cycle bases of reduced powers of graphs" (2016). *Applied Science Faculty and Graduate Publications*. 2.

https://publish.wm.edu/appliedsciencepub/2