The maximal exceptional graphs

Citation

Cvetkovic D, Lepovic M, Rowlinson P, Simic SK & Cvetkovic D (2002) The maximal exceptional graphs. Journal of Combinatorial Theory Series B, 86 (2), pp. 347-363. https://doi.org/10.1006/jctb.2002.2132

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 exceptional root system E8. We determine the maximal exceptional graphs by a computer search using the star complement technique, and then show how they can be found by theoretical considerations using a representation of E8 in R8. There are exactly 473 maximal exceptional graphs.

Keywords
graph; eigenvalue; star complement; root system

Journal
Journal of Combinatorial Theory Series B: Volume 86, Issue 2

People

Professor Peter Rowlinson

Emeritus Professor, Mathematics