On the structure of loop-free non-negative edge-bipartite graphs.

We continue the study of a class of signed graphs called finite connected loop-free edge-bipartite graphs Δ (bigraphs, for short), started in Simson (2013) [33] and continued in Gąsiorek et al. (2016) [14] and Simson-Zając (2017) [38]. In this paper we present an algorithmic approach to the study of non-negative bigraphs Δ with n + r ≥ 2 vertices of corank r ≥ 1 , that is, bigraphs with the symmetric Gram matrix G Δ : = 1 2 ( G ˇ Δ + G ˇ Δ t r) ∈ M n + r (1 2 Z) positive semi-definite of rank n ≥ 1 , where G ˇ Δ ∈ M n + r (Z) is the non-symmetric Gram matrix of Δ. One of the main results of this paper are Theorems 2.1 and 2.17 asserting that every such a bigraph Δ with n + r ≥ 2 vertices can be obtained from a corank zero (i.e. positive) connected loop-free bigraph Δ ′ with n ≥ 1 vertices by an r -point extension procedure (Δ ′ , u (1) , ... , u (r)) ↦ Δ : = Δ ′ [ [ u (1) , ... , u (r) ] ] along the r ≥ 1 roots u (1) , ... , u (r) ∈ Z n of the positive definite Gram form q Δ ′ : Z n → Z , v ↦ v G ˇ Δ ′ v t r. It is also shown that the extension procedure yields a combinatorial algorithm allowing us to obtain inductively all connected loop-free non-negative corank r ≥ 1 bigraphs with n + r ≥ 2 vertices, from the corank-zero bigraphs Δ ′ with n ≥ 1 vertices. [ABSTRACT FROM AUTHOR]