Bulletin, Classe des Sciences Mathématiques et Naturelles, Sciences mathématiques
Vol. CXXII, No. 26, pp. 115–131 (2001)
The maximal exceptional graphs with maximal degree less than $28$
D. Cvetkovic, P. Rowlinson and S.K. SimicDepartemnt of Mathematics, Faculty of Electrical Engineering, University of Belgrade, P.O. Box 35-54, 11120 Belgrade, Yugoslavia
Department of Computing Science and Mathematics, University of Stirling, Stirling FK9 4LA, Scotland
Department of Mathematics, Maritime Faculty Kotor, 85 330 Kotor, Dobrota 36, Montenegro, Yugoslavia
Abstract: A graph is said to be exceptional if it is connected, has least eigenvalue greater than or equal to $-2$, and is not a generalized line graph. Such graphs are known to be representable in the root system $E_8$. The 473 maximal exceptional graphs were found initially by computer, and the 467 with maximal degree $28$ have subsequently been characterized. Here we use constructions in $E_8$ to prove directly that there are just six maximal exceptional graphs with maximal degree less than 28.
Keywords: Graph, eigenvalue, root system
Classification (MSC2000): 05C50
Full text of the article: (for faster download, first choose a mirror)
Electronic fulltext finalized on: 20 Aug 2001. This page was last modified: 20 Jun 2011.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts