Algorithms computing \({\rm O}(n, \mathbb{Z})\)-orbits of \(P\)-critical edge-bipartite graphs and \(P\)-critical unit forms using Maple and C\#

• Date: 2018
• Main Authors: Polak, Agnieszka, Simson, Daniel
• Format: Article
• Language: English
• Published: Lugansk National Taras Shevchenko University 2018
• Subjects: edge-bipartite graph; unit quadratic form; \(P\)-critical edge-bipartite graph; Gram matrix; sincere root; orthogonal group; algorithm; Coxeter polynomial; Euclidean diagram; 15A63; 11Y16; 68W30; 05E10 16G20; 20B40; 15A21
• Online Access: https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1161
• Journal Title: Algebra and Discrete Mathematics

We present combinatorial algorithms constructing loop-free \(P\)-critical edge-bipartite (signed) graphs \(\Delta'\), with \(n\geq 3\) vertices, from pairs \((\Delta , w)\), with \(\Delta \) a positive edge-bipartite graph having \(n\mbox{-}1\) vertices and \(w\) a sincere root of \(\Delta \), up to an action \(*:\cal U \cal B igr_n \times {\rm O}(n,\mathbb{Z}) \to \cal U \cal B igr_n\) of the orthogonal group \({\rm O}(n,\mathbb{Z})\) on the set \(\cal U \cal B igr_n\) of loop-free edge-bipartite graphs, with \(n\geq 3\) vertices. Here \(\mathbb{Z}\) is the ring of integers. We also present a package of algorithms for a Coxeter spectral analysis of graphs in \(\cal U \cal B igr_n\) and for computing the \({\rm O}(n, \mathbb{Z})\)-orbits of \(P\)-critical graphs \(\Delta\) in \(\cal U \cal B igr_n\) as well as the positive ones. By applying the package, symbolic computations in Maple and numerical computations in C\#, we compute \(P\)-critical graphs in \(\cal U \cal B igr_n\) and connected positive graphs in \(\cal U \cal B igr_n\), together with their Coxeter polynomials, reduced Coxeter numbers, and the \({\rm  O}(n, \mathbb{Z})\)-orbits, for \(n\leq 10\). The computational results are presented in tables of Section 5.