Cycle Spaces of Digraphs

2016/09/28 by Chris Godsil, Godsil, Chris, Krystal Guo +1
Computer Science · Mathematics · #Graph theory and applications #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #math.CO #msc:05C50

paper · pdf · doi:10.48550/arxiv.1609.09118

9 pages, 2 figures

arxiv created 2016/09/28 · arxiv updated 2016/09/30

Abstract

The cycle space of a graph corresponds to the kernel of an incidence matrix. We investigate an analogous subspace for digraphs. In the case of digraphs of graphs, where every edge is replaced by two oppositely directed arcs, we give a combinatorial description of a basis of such a space. We are motivated by a connection to the transition matrices of discrete-time quantum walks.

Related

• The underlying digraph of a coined quantum random walk
• Graphs and their symmetries
• Cellular Algebras and Graph Invariants Based on Quantum Walks
• Relations between connected and self-avoiding walks in a digraph
• Digraphons: connectivity and spectral aspects