6 - The maximal exceptional graphs

Summary

This chapter is based on the recent publications [CvLRS2], [CvLRS3], [CvRS5] and [CvRS6]. In Section 6.1 we describe the outcome of the exhaustive computer search for the maximal exceptional graphs, obtained as extensions of 443 exceptional star complements. Inspection of these graphs motivates the results proved in Section 6.2 using representations in E₈. It is convenient to partition the maximal exceptional graphs into three types: (a) those which are cones of order 29, (b) those with maximal degree 28 and more than 29 vertices, (c) those with maximal degree less than 28. (We know from Chapter 3 that no vertex has degree greater than 28.) Our results reveal how the computing requirements can be drastically reduced. In particular, we show in Section 6.3 that the graphs of type (b) can be found as extensions of just one star complement, denoted by U₈. In Sections 6.4 and 6.5 we determine the graphs of type (c) without recourse to a computer, and in Section 6.6 we see that it follows that all graphs of type (b) or (c) have both U₈ and K₈ as a star complement for —2.

The computer search

We know from Theorem 5.3.1 that every maximal exceptional graph has an exceptional star complement for —2, and from Proposition 5.3.2 that such a star complement is one of the 443 graphs of order 8 described in part (v) of Theorem 2.3.20. Here, these star complements are labelled H001 to H443, ordered lexicographically by spectral moments; the graphs are listed in Table A2.