On polynomial time inflation algorithm for loop-free non-negative edge-bipartite graphs

摘要

We study a class of signed graphs called finite connected loop -free edge -bipartite graphs A (bigraphs, for short), started in Simson (2013) and continued in Simson and Zajac (2017) and Makuracki and Simson (2019). In this paper we present an algorithmic approach to the study of non-negative bigraphs A with n r > 1 vertices A0 = {al,, an+r},of corank r > 0, that is, bigraphs with the symmetric Gram matrix GA := L(GA GtAr) E - MnED positive semi-definite of rank n > 1, where GA E Mn r(Z) is the non-symmetric Gram matrix of A.