Biggs Theorem for Directed Cycles and Topological Invariants of Digraphs  

作　　者：Michael Hecht Ivo F. Sbalzarini Michael Hecht;Ivo F. Sbalzarini(Technische Universität Dresden, Faculty of Computer Science, Dresden, Germany;Max Planck Institute of Molecular Cell Biology and Genetics, Dresden, Germany;Center for Systems Biology Dresden, Dresden, Germany)

机构地区：[1]Technische Universitä t Dresden, Faculty of Computer Science, Dresden, Germany [2]Max Planck Institute of Molecular Cell Biology and Genetics, Dresden, Germany [3]Center for Systems Biology Dresden, Dresden, Germany

出　　处：《Advances in Pure Mathematics》2021年第6期573-594,共22页理论数学进展（英文）

摘　　要：We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #<em>P</em> hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as <em>graph embeddings</em>, <em>discrete Morse theory </em>and<em> graph clustering</em>.We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #<em>P</em> hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as <em>graph embeddings</em>, <em>discrete Morse theory </em>and<em> graph clustering</em>.

关 键 词：Biggs Theorem Elementary and Simple Cycles CW Complexes of Graphs Cellular and Singular Homology Betti Numbers 

分 类 号：O15[理学—数学]