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.
@article{856,
title = {Cycle bases of reduced powers of graphs},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {12},
year = {2016},
doi = {10.26493/1855-3974.856.4d2},
language = {EN},
url = {http://dml.mathdoc.fr/item/856}
}
Hammack, Richard H.; Smith, Gregory D. Cycle bases of reduced powers of graphs. ARS MATHEMATICA CONTEMPORANEA, Tome 12 (2016) . doi : 10.26493/1855-3974.856.4d2. http://gdmltest.u-ga.fr/item/856/