Complementary Pairs of Graphs With the Second Largest Eigenvalue not Exceeding (sqrt(5)-1)/2


Slobodan Simić


We characterize (in terms of minimal forbidden subgraphs) graphs having the following property: both the graph and its complement have the second largest eigenvalue not exceeding $(\sqrt{5}-1)/2$, i.e. the golden section. This characterization also enables us to find explicitely all graphs in question.