Numeric Algorithms for Corank Two Edge-bipartite Graphs and their Mesh Geometries of Roots

Abstract

Following a Coxeter spectral analysis problems for positive edge-bipartite graphs (signed multigraphs with a separation property) introduced in [SIAM J. Discr. Math. 27(2013), 827-854] and [Fund. Inform. 123(2013), 447-490], we study analogous problems for loop-free corank two edge-bipartite graphs Δ = (Δ₀,Δ₁). i.e. for edge-bipartite graphs Δ, with at least n = 3 vertices such that their rational symmetric Gram matrix G_Δ ∈ 𝕄 _n (ℚ) is positive semi-definite of rank n – 2. We study such connected edge-bipartite graphs by means of the non-symmetric Gram matrix Ğ_Δ ∈ 𝕄 _n (ℤ), the Coxeter matrix Cox_Δ := –Ğ_Δ · Ğ_Δ^–tr, its complex spectrum specc_Δ ⊆ ℂ, and an associated simply laced Dynkin diagram Dyn_Δ, with n – 2 vertices. Here ℤ means the ring of integers. It is well-known that if Δ ≈_ℤ Δ′ (i.e., there exists B ∈ 𝕄 _n (ℤ) such that det B = ±1 and Ğ_Δ′ = B^tr · Ğ_Δ · B) then specc_Δ = specc_Δ′ and Dyn_Δ = Dyn_Δ′.

A complete classification of connected non-negative loop-free edge-bipartite graphs Δ with at most six vertices of corank two, up to the ℤ-congruence Δ ≈_ℤ Δ′, is also given. A complete list of representatives of the ℤ-congruence classes of all connected non-negative edge-bipartite graphs of corank two with with at most 6 vertices is constructed; it consists of 1, 2, 2 and 8 edge-bipartite graphs of corank two with 3, 4, 5 and 6 vertices, respectively.