4 - Regular graphs

Summary

Some general properties of regular exceptional graphs, including a relation between the order and degree of such graphs, are given in Section 4.1. In Section 4.2 we establish a spectral characterization of regular line graphs: we use the methods of [CvDo2], and a reformulation of results from [BuCS1] and [BuCS2], to provide a computer-free proof. Some characterizations of special classes of line graphs are given in Section 4.3. The regular exceptional graphs are determined in Section 4.4: they were first found in [BuCS1], but are derived here in a more economical way, partly using arguments from [BrCN].

Regular exceptional graphs

In this section we determine some general properties of regular exceptional graphs, beginning with the following observation.

By Proposition 1.1.9, a regular connected generalized line graph is either a line graph or a cocktail party graph. In view of Theorems 3.6.1 and 3.6.3, the following theorem is now straightforward.

Theorem 4.1.1. If G is a regular connected graph with least eigenvalue —2, then one of the following holds:

(i) G is a line graph,

(ii) G is a cocktail party graph, or

(iii) G is an exceptional graph (with a representation in E₈).

The next result imposes strong restrictions on the possibilities which can arise in Theorem 4.1.1(iii). Recall that a principal eigenvalue is an eigenvalue greater than —2.

Proposition 4.1.2.The number of principal eigenvalues of an exceptional graph is 6, 7 or 8.

Proof. Let G be an exceptional graph with r principal eigenvalues. We know from Section 3.6 that G has an a-representation R in E₈, but no such representation in D_n for any n.