Regular graphs with four eigenvalues
In a recent research project, Edwin van Dam and I worked on the classification of all regular graphs on at most 30 vertices that have four distinct eigenvalues. We present our results in a forthcoming paper entitled " Small regular graphs with four eigenvalues". There we list what we call "feasible spectra" for such graphs on at most 30 vertices. Of the 244 feasible spectra found we have classified all graphs, or shown that none exists, in 213 cases. Of the other 31 there are some graphs in 13 cases (incomplete computer search), while the remaining 18 cases are completely open. In two particular cases it has not been possible to complete the computer search, but we know of the existence of transitive graphs which were found in a classification of transitive graphs on 24 vertices that was undertaken by Gordon Royle et al. These are graphs on 24 vertices with spectra [91, 37, -19, -37] and [111, 37, -18, -38]. There are, respectively, 2 and 3 transitive graphs with these spectra. As yet we do not know of the existence of any others.
I have arranged the graphs that we found into two lists, the first comprising those graphs for which all four eigenvalues are integral, and the second deals with the case when there are just two integral eigenvalues. Some, or all, of these graphs that have been classified, may be obtained from this site by downloading the appropriate files itemised below. I have split each of the two lists referred to above into subclasses comprising graphs with the same number of vertices. Thus, for example, the file I.graphs.24.gz contains a gzipped file of all graphs on 24 vertices having four integral eigenvalues that were found in our investigation. Since the file containing graphs on 30 vertices would be too large I have split it into two, I.graphs.30.1.gz and I.graphs.30.2.gz..
Within each file there are separate lists comprising those graphs with different spectra but the same number of vertices. To save space, each graph is listed in hexadecimal form. This is obtained by concatenating the rows of the upper triangular part of the adjacency matrix of the graph and writing the resulting binary integer (after padding it out with zeros to make its length divisible by 4) as a hexadecimal integer. I also give the order of the autmorphism group and the orbits under the action of the group, assuming that the group is neither trivial nor transitive. Since the smallest number of vertices for which a computer was actually needed to construct a graph was 18, we only list graphs on v vertices, where 18 <= v <= 30.