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

Abstract

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.