Cycle bases of reduced powers of graphs

Richard H. Hammack ; Gregory D. Smith

Ars Mathematica Contemporanea, Tome 12 (2017) no. 1, pp. 183-203.

Résumé

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.

Détail

DOI : 10.26493/1855-3974.856.4d2

Keywords: Graph products, Markov chains, cycle spaces