Graphs with small spectral gap

Abstract

It is conjectured that connected graphs with given number of vertices and minimum spectral gap (i.e., the difference between their two largest eigenvalues) are double kite graphs. The conjecture is confirmed for connected graphs with at most 10 vertices, and, using variable neighbourhood metaheuristic, there is evidence that it is true for graphs with at most 15 vertices. Several spectral properties of double kite graphs are obtained, including the equations for their first two eigenvalues. No counterexamples to the conjecture are obtained. Some numerical computations and comparisons that indicate its correctness are also given. Next, 3 lower and 3 upper bounds on spectral gap are derived, and some spectral and structural properties of the graphs that minimize the spectral gap are given. At the end, it is shown that in connected graphs any double kite graph has a unique spectrum.