A Gram classification of principal Cox-regular edge-bipartite graphs via inflation algorithm.

Abstract The paper is devoted to a Gram classification of an important class of signed graphs with loops playing an important role in many branches of mathematics, physics and computer science including game theory, crystallography, Diophantine geometry, Lie theory, spectral graph theory, a graph coloring technique, algebraic methods in graph theory. They have many deep applications in spectral machine learning methods, electrical networks, to link sign prediction in signed unipartite and bipartite networks, and community partition in social networks. We continue the study of finite connected edge-bipartite graphs Δ (bigraphs, for short), with m ≥ 2 vertices (a class of signed graphs), started in Simson (2013) and developed in Simson (2016) by means of the non-symmetric Gram matrix G ˇ Δ ∈ M m (Z) defining Δ , its symmetric Gram matrix G Δ : = 1 2 [ G ˇ Δ + G ˇ Δ t r ] ∈ M m (1 2 Z) , and the Gram quadratic form q Δ : Z m → Z. In the present paper, given n ≥ 1 , we mainly study connected principal Cox-regular edge-bipartite graphs Δ with loops and n + 1 ≥ 2 vertices, in the sense that the symmetric Gram matrix G Δ ∈ M n + 1 (Z) of Δ is positive semi-definite of rank n ≥ 1. Our aim is to classify such edge-bipartite graphs by means of an inflation algorithm, up to the weak Gram Z -congruence Δ ∼ Z Δ ′ , where Δ ∼ Z Δ ′ means that G Δ ′ = B t r ⋅ G Δ ⋅ B , for some B ∈ M n + 1 (Z) with det B = ± 1. Our main result of the paper asserts that, given a principal Cox-regular connected edge-bipartite graph Δ with n + 1 ≥ 2 vertices, there exists an edge-bipartite Euclidean graph D n + 1 of Tables A and B, and a suitably chosen sequence t • − of the inflation operators, each of one of the forms Δ ′ ↦ t a − Δ ′ or Δ ′ ↦ t a b − Δ ′ , such that the composite operator Δ ↦ t • − Δ reduces Δ to the bigraph D n + 1 such that: (i) Δ ∼ Z D n + 1 and (ii) the bigraphs Δ , and D n + 1 have the same number of loops. The algorithm does not change loops and computes a matrix B ∈ M n + 1 (Z) , with det B = ± 1 , defining the weak Gram Z -congruence Δ ∼ Z D n + 1 , that is, satisfying the equation G D n + 1 = B t r ⋅ G Δ ⋅ B. [ABSTRACT FROM AUTHOR]