ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 Mathematical Subject Classification: 05C Simić, Slobodan, University of Belgrade, Yugoslavia: On graphs whose second largest eigenvalue does not exceed the golden section The spectrum of a graph is the spectrum of its adjacency matrix. Graphs whose second largest eigenvalue does not exceed the golden section, i. e. \frac{\sqrt{5}−1}{2}, as recently proved, can be characterized by a \underline{f}inite collection of minimal forbidden (induced) subgraphs. By combining theoretical results and computer search (including symbolic calculations) we find not only all the forbidden subgraphs, but also all sequences of graphs (determined by one or more integral parameters) having the limiting points less than or equal to golden section. Part of these results is a joint work with D. Cvetković.