Cycle bases of reduced powers of graphs - Hammack, Richard H. (Ars mathematica contemporanea, 2017)
We define what appears to be a new construction. Given a graph ?$G$? and a positive integer ?$k$?, the reduced ?$k$?th 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: grafi; markovske verige; produkti grafov; prostori ciklov