Inflation Agorithm for Cox-regular Postive Edge-bipartite Graphs with Loops

Abstract

We continue the study of finite connected edge-bipartite graphs Δ, with m ≥ 2 vertices (a class of signed graphs), started in [SIAM J. Discrete Math. 27(2013), 827-854] and developed in [Fund. Inform. 139(2015), 249-275, 145(2016), 19-48] by means of the non-symmetric Gram matrix ${\stackrel{\vee }{G}}_{\Delta }\in {𝕄}_n(\mathbb{Z})$ defining Δ, its symmetric Gram matrix $G_{\Delta }:=\frac{1}{2}\left[\stackrel{\vee }{G_{\Delta }}+\stackrel{\vee }{G_{\Delta }^{tr}}\right]\in {𝕄}_n(\frac{1}{2}\mathbb{Z})$, and the Gram quadratic form q_Δ : ℤⁿ → ℤ. In the present paper we study connected positive Cox-regular edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense that the symmetric Gram matrix G_Δ ∈ 𝕄 _n (ℤ) of Δ is positive definite. Our aim is to classify such Cox-regular edge-bipartite graphs with at least one loop by means of an inflation algorithm, up to the weak Gram ℤ-congruence Δ ~_ℤ Δ′, where Δ ~_ℤ Δ′ means that G_Δ′ = B^tr · G_Δ · B, for some B ∈ 𝕄 _n (ℤ) such that det B = ±1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Δ with n ≥ 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph 𝒟 _n ∨ {ℬ _n , 𝒞 _n , ℱ₄, 𝒢₂} with loops and a suitably chosen sequence ${\text{t}}_{•}^{-}$ of the inflation operators of one of the types ${\Delta }^{\prime }\mapsto {\text{t}}_a^{-}{\Delta }^{\prime }$ and ${\Delta }^{\prime }\mapsto {\text{t}}_{ab}^{-}{\Delta }^{\prime }$ such that the composite operator $\Delta \mapsto {\text{t}}_{•}^{-}\Delta$ reduces Δ to the bigraph 𝒟 _n such that Δ ~_ℤ 𝒟 _n and the bigraphs Δ, 𝒟 _n have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B ∈ 𝕄 _n (ℤ), with det B = ±1, defining the weak Gram ℤ-congruence Δ ~_ℤ 𝒟 _n , that is, satisfying the equation G_{𝒟 n} = B^tr · G_Δ · B.