Cycle bases of reduced powers of graphs

DOI10.26493/1855-3974.856.4D2MaRDI QIDQ5357298zbMATH OpenOpenAlexFDO

Authors Gregory D. Smith, Richard H. Hammack

Publication date 14 September 2017

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.02896

zbMATH Keywords

cycle spacesgraph productsMarkov chains

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Continuous-time Markov processes on discrete state spaces (60J27)

Abstract: 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. The reduced power $G^{(k)}$ is the transition graph of the master Markov chain for $k$ identical and indistinguishable stochastic automata with transition graph $G$. 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)}$. Minimum cycle bases of reduced graph powers are especially relevant to applications that do not allow state-dependent coupling of automata to introduce nonequilibrium steady states. This paper also demonstrates how our minimum cycle basis construction provides conditions that ensure against violations of microscopic reversibility. In addition, the minimum cycle basis construction is an interesting combinatorial problem in itself.

Recommendations

• On power graphs of cycles
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Length bounds for cycle bases of graphs
• Minimum cycle bases of graphs over different fields
• The basis number of the powers of the complete graph
• Minimum cycle bases of Halin graphs
• Shortest co-cycle bases of graphs
• Minimum cycle bases of direct products of complete graphs
• Minimum cycle bases of direct products of graphs with cycles
• Powers of cycles, powers of paths, and distance graphs

Cited in

(5)

• Augmented and restricted base loci of cycles
• A Schrödinger operator approach to higher spin XXZ systems on general graphs
• scientific article; zbMATH DE number 2197947 (Why is no real title available?)
• A novel discussion on power fuzzy graphs and their application in decision making
• On some metric properties of supertoken graphs

This page was built for publication: Cycle bases of reduced powers of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5357298)