The maximal exceptional graphs with maximal degree less than 28. (English) Zbl 0997.05060

A graph is said to be exceptional if it is connected, its smallest eigenvalue is greater than or equal to \(-2\), and it is not a generalized line graph. Such graphs occur in connection with the root system \(E_8\). The maximal vertex degree of an exceptional graph does not exceed 28. In an earlier, but hitherto unpublished, work the authors and M. Lepović established that there are exactly 473 exceptional graphs, and that 467 of them have maximal vertex degree equal to 28. The remaining six exceptional graphs with maximal vertex degree less than 28 were recently determined by the same authors, see D. Cvetković, P. Rowlinson and S. K. Simić [Constructions of the maximal exceptional graphs with largest degree less than 28, Report CSM–156, University of Stirling (2000)]. The authors outline an another approach towards the characterization of the same six exceptional graphs, based on constructions in the \(E_8\) root system.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory
Full Text: EuDML