Spectra of signed graphs with two eigenvalues

Abstract

In this paper we study connected signed graphs with 2 eigenvalues from several (theoretical and computational) perspectives. We give some basic results concerning the eigenvalues and cyclic structure of such signed graphs; in particular, we complete the list of those that are 3 or 4-regular. There is a natural relation between signed graphs and systems of lines in a Euclidean space that are pairwise orthogonal or at fixed angle, with a special role of those with 2 eigenvalues. In this context we derive a relative bound for the number of such lines (an extension of the similar bound related to unsigned graphs). We also determine all such graphs whose negative eigenvalue in not less than −2, except for so-called exceptional signed graphs. Using the computer search, we determine those with at most 10 vertices. Several constructions are given and the possible spectra of those with at most 30 vertices are listed.