We study nonregular graphs with three eigenvalues. We determine all the ones with least eigenvalue &2, and give new infinite families of examples. 1998 Academic Press
1. Introduction
In this paper we look at the graphs that are generalizations of strongly regular graphs (cf. [3, 6, 16]) by dropping the regularity condition. More specifically, we consider graphs of which the adjacency matrices have three distinct eigenvalues. Seidel (cf. [15]) did a similar thing for the Seidel matrix by introducing strong graphs, which turned out to have an easy combinatorial characterization. Similarly, a nice combinatorial characterization is found for graphs with three Laplace eigenvalues [9]. The problem of graphs with few eigenvalues was perhaps first raised by Doob [11]. For more on such graphs we refer to [8].
Regular graphs with three eigenvalues are well-known to be strongly regular. Therefore we focus on the nonregular graphs, with three (adjacency) eigenvalues. Here the combinatorial simplicity seems to disappear with the regularity. This all lies in the algebraic consequence that the all-one vector is no longer an eigenvector. The Perron Frobenius eigenvector still contains a lot of information, but the problem is to derive this eigenvector from the spectrum.
Earlier results on nonregular graphs with three eigenvalues were found by Bridges and Mena [2] and Muzychuk and Klin [14]. In this paper we determine all the ones with least eigenvalue &2, and give new families of examples by using symmetric designs, affine designs, antipodal covers of the complete graph, and systems of linked symmetric designs.