The graphs with all but two eigenvalues equal to ± 1

2013/10/24 by Cioabă, Sebastian M., Haemers, Willem H., Vermette, Jason +1
#05B20 #05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1310.6529

Abstract

We determine all graphs whose adjacency matrix has at most two eigenvalues (multiplicities included) different from ± 1 and decide which of these graphs are determined by their spectrum. This includes the so-called friendship graphs, which consist of a number of edge-disjoint triangles meeting in one vertex. It turns out that the friendship graph is determined by its spectrum, except when the number of triangles equals sixteen.

Related

• The graphs with all but two eigenvalues equal to 2 or -1
• The graphs with all but two eigenvalues equal to -2 or 0
• The signed graphs with two eigenvalues unequal to ± 1
• Connected graphs cospectral with a Friendship graph
• Graphs cospectral with a friendship graph or its complement