From finite line graphs to infinite derived signed graphs

摘要

Let X be a subset of {±α ± β: α, β ∈ ? and α ≠ β} where B is an orthonormal set in an inner product space over R, such that x ∈ X ? -x ∈ X. Then the signed graph which is defined as described below is called a derived signed graph: its vertex set is X; two vertices x, y are joined by a positive (negative) edge when (x,y) is positive (negative); when (x,y) = 0, x, y are not joined. Let D denote the family of all derived signed graphs-the order of a member of D may be infinite. (The family of all generalized line graphsline graphs belong to this family-is a subfamily of D.) Let M be the class of all minimal nonderivable signed graphs. [M includes the 31 (finite) minimal nongeneralized line graphs computed by various methods in the literature.] In this article, we characterize D, determine M and classify the family of all signed graphs S for which, the following holds: for each finite subset X of V(S), the least eigenvalue of S[X] is at least -2. The third result substantially generalizes the well known result (Cameron et al. (1976) [1]) on classifying the family of all finite (signed) graphs with least eigenvalues ≥ -2.