2017/12/05 by Haemers, Willem H.
#05C50 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1712.01749
A mixed extension of a graph G is a graph H obtained from G by replacing each vertex of G by a clique or a coclique, where vertices of H coming from different vertices of G are adjacent if and only if the original vertices are adjacent in G. If G has no more than three vertices, H has all but at most three adjacency eigenvalues equal to 0 or -1. In this paper we consider the converse problem, and determine the class \cal G of all graphs with at most three eigenvalues unequal to 0 and -1. Ignoring isolated vertices, we find that \cal G consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths P4 and P5.