Back to Search
Start Over
On the structure of loop-free non-negative edge-bipartite graphs.
- Source :
-
Linear Algebra & its Applications . Oct2019, Vol. 579, p262-283. 22p. - Publication Year :
- 2019
-
Abstract
- 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]
- Subjects :
- *SYMMETRIC matrices
*COMBINATORICS
Subjects
Details
- Language :
- English
- ISSN :
- 00243795
- Volume :
- 579
- Database :
- Academic Search Index
- Journal :
- Linear Algebra & its Applications
- Publication Type :
- Academic Journal
- Accession number :
- 137777124
- Full Text :
- https://doi.org/10.1016/j.laa.2019.06.002