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

A. Polak ; D. Simson

Algebra and discrete mathematics, Tome 16 (2013) no. 2, pp. 242-286

Résumé

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-1$ vertices and $w$ a sincere root of $\Delta $, up to an action $*:\mathcal{U} \mathcal{B} igr_n \times {\rm O}(n,\mathbb{Z}) \to \mathcal{U}\mathcal{B} igr_n$ of the orthogonal group ${\rm O}(n,\mathbb{Z})$ on the set $\mathcal{U} \mathcal{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 $\mathcal{U} \mathcal{B} igr_n$ and for computing the ${\rm O}(n, \mathbb{Z})$-orbits of $P$-critical graphs $\Delta$ in $\mathcal{U} \mathcal{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 $\mathcal{U} \mathcal{B} igr_n$ and connected positive graphs in $\mathcal{U} \mathcal{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.

Détail

Keywords: unit quadratic form, $P$-critical edge-bipartite graph, sincere root, algorithm, Euclidean diagram.
Mots-clés : edge-bipartite graph, Gram matrix, orthogonal group, Coxeter polynomial