Bulletin T.CXXII de l’Académie Serbe des Sciences et des Arts - 2001 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 26

THE MAXIMAL EXCEPTIONAL GRAPHS WITH MAXIMAL DEGREE LESS THAN 28

D. CVETKOVIĆ, P. ROWLINSON, S.K. SIMIĆ

(Presented at the 4th Meeting, held May 25, 2001)

A b s t r a c t. 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.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: Graph, eigenvalue, root system

1. Introduction

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. Generalized line graphs have been studied in [9, 14], while exceptional graphs first appeared in the context of spectral characterizations of certain classes of line graphs by A. J. Hoffman and others in the 1960s (see, for example, [12, pp.

12-14]). The key paper [5] introduced root systems as a means of investigating graphs with least eigenvalue −2; in particular it was shown by this technique that an exceptional graph has at most 36 vertices and each vertex has degree at most 28. The regular exceptional graphs, 187 in number, were found in [2, 3], but the problem of finding a suitable description of all the exceptional graphs remained open. Much information on these topics can be found in the monographs [1, 6, 8] and in the expository paper [4]. We described in [11] the results of an exhaustive computer search for the exceptional graphs which are maximal in the sense that every exceptional graph is an induced subgraph of (at least) one such graph. These graphs, 473 in all, were found as maximal extensions of appropriate star complements (cf. [10, 13, 14, 17] and below). An independent means of constructing those with maximal degree 28 was included in [11]: the crucial property is that the neighbours of a vertex of degree 28 induce a subgraph which is switchingequivalent to the line graph L(K_{8}) and hence determined by a 2-colouring of the edges of K_{8}. In [15] we used a variant of this approach to obtain various constructions for the maximal exceptional graphs with maximal degree less than 28, but the number of isomorphism classes was not verified. Here we determine these ‘exceptional maximal exceptional graphs’ directly from the root system E_{8} and prove that there are precisely six of them. They are necessarily the graphs labelled M001, M002, M417, M428, M437, M462 in [11], and definitions of them appear below. The graph M001 was identified in [16] as a non-regular graph with just three distinct eigenvalues.

It is well known that an exceptional graph G is representable in the root system E_{8} (see [6, Chapter 3] or [1, Chapter 3]). This means that if G has A as a (0, 1)-adjacency matrix then I + \frac{1}{2}A is the Gram matrix of a set of normalized vectors in E_{8}; explicitly, if {e_{1}, …, e_{8}} is an orthonormal basis for IR^{8} then 8I + 4A is the Gram matrix of a subset of the following set of 240 vectors (cf. [2, 11]):

type a: 28 vectors of the form a_{ij} = 2e_{i} + 2e_{j}; i, j = 1, …, 8, i < j; type a′: 28 vectors opposite to those of type a; type b: 28 vectors of the form b_{ij} = −2e_{i} − 2e_{j} + ∑_{k=1}^{8} e_{k}; type b′: 28 vectors opposite to those of type b; type c: 56 vectors of the form c_{ij} = 2e_{i} − 2e_{j}; i, j = 1, …, 8, i ≠ j; type d: 70 vectors of the form d_{ijkl} = −2e_{i} − 2e_{j} − 2e_{k} − 2e_{l} + ∑_{s=1}^{8} e_{s}

with distinct i, j, k, l ∈ {1, …, 8}; type e: 2 vectors e and −e, where e = ∑_{i=1}^{8} e_{i}.

These 240 vectors determine 120 lines at 60^{∘} or 90^{∘}. Let Γ denote the graph which has these lines as vertices, with two vertices adjacent if and only if the corresponding lines are orthogonal. We recall from [7, p.85] some properties of the automorphism group of Γ (communicated by P. J. Cameron). This group has as a subgroup of index 2 the orthogonal group O^{+}(8, 2), which is transitive on the vertices of Γ. Moreover the stabilizer of a vertex v acts as a rank 3 group on the subgraph Γ(v) induced by the neighbours of v; in particular, the stabilizer of v is edge-transitive on Γ(v).

By a representation of the exceptional graph G we mean a subset R(G) of E_{8} whose Gram matrix is a scalar multiple of 8I + 4A, where A is the adjacency matrix of G. Note that if R(G) is a representation of G then so is −R(G) = {−u : u ∈ R(G)}. In view of the transitivity of Aut(Γ), we can therefore assume that e represents a vertex of maximal degree, and in this case we call R(G) a standard representation. Note that then no vector of type a′, b′ features in R(G); moreover a second standard representation is given by ϕ(R(G)) where the involutory map ϕ is defined by: ϕ(e) = e, ϕ(a_{ij}) = b_{ij}, ϕ(b_{ij}) = a_{ij}, ϕ(c_{ij}) = c_{ji}(−c_{ij}), ϕ(d_{ijkl}) = d\overline{ijkl}(= −d_{ijkl}). We refer to R(G) and ϕ(R(G)) as dual representations. (Accordingly we may assume if necessary that the number of vectors of type b in R(G) does not exceed the number of vectors of type a.) We give standard representations of the graphs M001, M002, M417, M428, M437 and M462:

• M001 (22 vertices, with degrees 16^{14}, 7^{8}; the vertices of degree 16 induce the cocktail-party graph \overline{7K_{2}}, while those of degree 7 form a coclique) a_{ij}(ij = 12, 13, 14, 15, 23, 24, 26, 34, 37, 48); b_{ij}(ij = 56, 57, 58, 67, 68, 78); c_{ij}(ij = 15, 26, 37, 48); d_{5678}; e.

• M002 (28 vertices, with degrees 22^{7}, 16^{14}, 10^{7}; the vertices of degree 10 form a coclique) a_{ij}(ij = 12, 13, 14, 17, 18, 23, 25, 27, 28, 36, 37, 38, 78); b_{ij}(ij = 45, 46, 47, 48, 56, 57, 58, 67, 68); c_{ij}(ij = 14, 25, 36); d_{4567}, d_{4568}; e.

• M417 (29 vertices, with degrees 26^{1}, 24^{2}, 18^{16}, 12^{8}, 10^{2})

a_{ij}(ij = 12, 15, 16, 17, 18, 25, 26, 27, 28, 57, 68);

b_{ij}(ij = 13, 24, 34, 35, 36, 37, 38, 45, 46, 47, 48, 56, 58, 67, 78);

c_{13}, c_{24}; e.

• M428 (29 vertices, with degrees 26^{2}, 22^{1}, 18^{16}, 14^{6}, 10^{4})

a_{ij}(ij = 12, 15, 16, 17, 18, 25, 26, 27, 28); b_{ij}(ij = 13, 24, 34, 35, 36, 37, 38, 45, 46, 47, 48, 56, 57, 58, 67, 68, 78); c_{13}, c_{24}; e.

• M437 (30 vertices, with degrees 26^{2}, 24^{1}, 20^{8}, 17^{8}, 16^{1}, 14^{2}, 13^{4}, 11^{4}) a_{ij}(ij = 12, 15, 16, 17, 18, 25, 26, 27, 28, 56); b_{ij}(ij = 13, 24, 34, 35, 36, 37, 38, 45, 46, 47, 48, 57, 58, 67, 68, 78); c_{13}, c_{24}; d_{3478}; e.

• M462 (31 vertices, with degrees 26^{3}, 22^{4}, 19^{8}, 16^{4}, 15^{6}, 12^{6}) a_{ij}(ij = 12, 15, 16, 17, 18, 25, 26, 27, 28, 56, 67); b_{ij}(ij = 13, 24, 34, 35, 36, 37, 38, 45, 46, 47, 48, 57, 58, 68, 78); c_{13}, c_{24}; d_{3458}, d_{3478}; e.

These standard representations are not unique; indeed others arise in the course of our constructions, and in such cases we specify an isomorphism with one of the above graphs. The isomorphisms are found by means of star complements, as we now explain. We write V (G) for the set of vertices of the graph G, and Δ(v) for the set of neighbours of the vertex v. Further, if H is a subgraph of G then Δ_{H}(v) = Δ(v) ∩ V (H).

Recall that if μ is an eigenvalue of G with multiplicity k, then a star complement for μ is an induced subgraph H = G − X(X ⊆ V (G)) such that |X| = k and μ is not an eigenvalue of G − X. If μ ∉ {−1, 0} then the H-neigbourhoods Δ_{H}(v)(v ∉ V (H)) are distinct [12, Corollary 7.3.6]. Now let G, G′ be graphs with H, H′ respectively as star complements for μ, where μ ≠ −1, 0. If ψ is an isomorphism H → H′ such that ψ maps the neigbourhoods Δ_{H}(v)(v ∉ V (H)) onto the neighbourhoods Δ_{H′}(v′)(v′ ∉ V (H′)) then by the Reconstruction Theorem [12, Theorem 7.4.1], ψ extends to an isomorphism G → G′, defined outside H by ψ(Δ_{H}(v)) = Δ_{H′}(ψ(v)). For the six graphs above, the isomorphisms required in Section 4 are constructed using star complements for −2 isomorphic to \overline{K_{1,2} ∪ 5K_{1}}, the graph labelled E443 in [11].

In a standard representation R(G) of an exceptional graph G, the following are the pairs of vectors which are incompatible because they have inner product −4.

(CC) c_{ij} and c_{jk},

(DD) d_{ijkl} and d_{i′j′k′l′} whenever |{i, j, k, l} ∩ {i′, j′, k′, l′}| ≤ 1,

(AB) a_{ij} and b_{ij},

(AC) a_{ij} and c_{hj}(h ≠ i, j), a_{ij} and c_{hi}(h ≠ i, j), (AD) a_{uv} and d_{ijkl} whenever {u, v} ⊆ {i, j, k, l},

(BC) b_{ij} and c_{ik}(k ≠ i, j), b_{ij} and c_{jk}(k ≠ i, j),

(BD) b_{uv} and d_{ijkl} whenever {u, v} ∩ {i, j, k, l} = ∅,

(CD) c_{uv} and d_{ijkl} whenever {u, v} ∩ {i, j, k, l} = {u}.

The following consequence is a reformulation of [11, Theorem 3.6].

Lemma 1.1. If for some pair i, j the vectors a_{ij} and b_{ij} are absent from a standard representation R(G) of a maximal exceptional graph G then R(G) includes vectors v and w such that e, v, w are pairwise orthogonal.

P r o o f. By the maximality of G, a_{ij} and b_{ij} are excluded by the presence of certain vectors, which in view of the complete list of incompatibilities above, are of type c or d. Now the vectors of type c or d which exclude a_{ij} are those in the set A_{ij} comprising c_{hi}(h ≠ i, j), c_{hj}(h ≠ i, j) and the vectors d_{pqrs} for which {i, j} ⊆ {p, q, r, s}. Those which exclude b_{ij} are those in the set B_{ij} comprising c_{ik}(k ≠ i, j), c_{jk}(k ≠ i, j) and the vectors d_{pqrs} for which {i, j} ∩ {p, q, r, s} = ∅. Note that the inner product of any vector in A_{ij} with any vector in B_{ij} is non-positive; in particular, two orthogonal vectors v and w, each of type c or d, must be present. Since these vectors are orthogonal to e the Lemma is proved. □

Henceforth we consider a standard representation R(G) of a maximal exceptional graph G with maximal degree less than 28.

In Aut(Γ), the stabilizer of the line ⟨e⟩ is edge-transitive on the subgraph induced by the neighbours of ⟨e⟩ and so in view of Lemma 1.1 we may assume that R(G) contains two orthogonal vectors v, w of type c. (Alternative representations, in which at least one of the vectors v, w is of type d, will be described elsewhere.) Let θ be the maximum number of pairwise orthogonal vectors of type c in R(G), and note that 2 ≤ θ ≤ 4. We analyze the cases θ = 4, 3, 2 in Sections 2,3,4, respectively. When θ = 4 we find that G is M001; when θ = 3 we find that G is M002; and when θ = 2 we find that G is one of M001, M002, M417, M428, M437, M462. We may summarize the results as follows.

Main Theorem. If G is a maximal exceptional graph in which every vertex has degree less than 28 then G is isomorphic to one of M001, M002, M417, M428, M437 and M462.

In the sequel we identify vertices of G with corresponding vectors in R(G).

2. The case θ = 4

Without loss of generality, R(G) contains the vectors c_{15}, c_{26}, c_{37}, c_{48}. In view of the incompatibilities (AC), (BC), (CC) the further possible

vectors of types a, b, c in R(G) are

a_{ij}(ij = 12, 13, 14, 23, 24, 34, 15, 26, 37, 48);
b_{ij}(ij = 15, 26, 37, 48, 56, 57, 58, 67, 68, 78);

and

c_{ij}(ij = 16, 17, 18, 25, 27, 28, 35, 36, 38, 45, 46, 47).

Moreover, if d_{ijkl} is present then |{i, j, k, l} ∩ {5, 6, 7, 8}| ≥ 2. (For example, neither d_{1234} nor d_{2345} is compatible with c_{26}.) It follows that d_{5678} is compatible with all possible vectors, hence is present by maximality. Now d_{5678} is adjacent to each of c_{15}, c_{26}, c_{37}, c_{48}, and is adjacent to all possible neighbours of e except a_{ij} and b_{ij}(ij = 15, 26, 37, 48).

Recall now that deg(e) ≥ deg(d_{5678}), while for given ij at most one of a_{ij}, b_{ij} is present. It follows that (i) deg(e) = deg(d_{5678}); (ii) one of a_{ij}, b_{ij} is present for each ij = 15, 26, 37, 48; (iii) no further vectors of type c are present (for any such vector would be adjacent to d_{5678}); (iv) similarly, if another vector d_{ijkl} is present then |{i, j, k, l} ∩ {5, 6, 7, 8}| = 2.

It follows from (iv) by (CD) that the only possible vectors of type d are d_{ijkl} for ijkl = 1256, 1357, 1458, 2367, 2468, 3478.

Next we show that either all a_{ij}(ij = 15, 26, 37, 48) are present or all b_{ij}(ij = 15, 26, 37, 48) are present. Without loss of generality, suppose by way of contradiction that a_{15} and b_{26} are present. Then the vectors d_{ijkl}(ijkl = 1256, 1357, 1458, 3478) are excluded and d_{2678} is compatible with all of the possible vectors remaining; but then by maximality d_{2678} is present, a contradiction.

The presence of a_{ij}(ij = 15, 26, 37, 48) or b_{ij}(ij = 15, 26, 37, 48) now excludes all possible vectors of type d other than d_{5678}, and so there remain just two possible maximal sets of 22 pairwise compatible vectors. By duality we may assume that the number of vectors of type b does not exceed the number of vectors of type a. Accordingly just one graph arises, namely the graph M001 defined in Section 1.

3. The case θ = 3

Without loss of generality suppose that {c_{14}, c_{25}, c_{36}} is a largest set of pairwise orthogonal vectors of type c. In view of the incompatibilities (AC), (BC), (CC) the further possible vectors of types a, b, c in R(G) are

a_{ij}(ij = 12, 13, 17, 18, 23, 27, 28, 37, 38, 78, 14, 25, 36);
b_{ij}(ij = 45, 46, 47, 48, 56, 57, 58, 67, 68, 78, 14, 25, 36);

and

c_{ij}(ij = 15, 16, 17, 18, 24, 26, 27, 28, 34, 35, 37, 38, 74, 75, 76, 84, 85, 86).

Moreover, if d_{ijkl} is present then by (CD) either |{i, j, k, l}∩{4, 5, 6}| ≥ 2 or ijkl ∈ {1478, 2578, 3678}.

Now the compatible vectors d_{4567}, d_{4568} are compatible with all possible vectors, and are therefore present by maximality.

We show next that the vectors a_{12}, a_{13}, a_{23} and b_{45}, b_{46}, b_{56} are all present. If a_{12} is absent it must be excluded by d_{1245}, and if b_{45} is absent it must be excluded by d_{3678}. (The reasons are that a_{12}, b_{45} are compatible with all possible vectors of type c, while any vector of type d which is present must be compatible with c_{14} and c_{25}.) If d_{1245} is present then d_{3678} is absent and so a_{45} is present; but then deg(b_{45}) > deg(e) since a_{14}, a_{25}, b_{67}, b_{68}, b_{78}, b_{36} are excluded. Similarly, if d_{3678} is present then b_{12} is present and deg(a_{12}) > deg(e). In either case we have a contradiction and so a_{12}, b_{45} are present. Similarly, a_{13}, b_{46} are present and a_{23}, b_{56} are present.

Let

S = {a_{ij} : ij = 37, 38, 78, 14, 25, 36} ∪ {b_{ij} : ij = 67, 68, 78, 14, 25, 36},

T = {a_{ij} : ij = 13, 17, 18, 23, 27, 28} ∪ {b_{ij} : ij = 46, 47, 48, 56, 57, 58},

and let α be the number of adjacencies between {a_{12}, b_{45}} and vectors of type c or d.

Note that the elements of T ∩Δ(e), together with e, c_{14}, c_{25}, d_{4567}, d_{4568}, are adjacent to both a_{12} and b_{45}; while those of S ∩ Δ(e), together with {a_{12}, b_{45}}, are adjacent to just one of a_{12}, b_{45}. It follows that

deg(a_{12}) + deg(b_{45}) = |S ∩ Δ(e)| + 2|T ∩ Δ(e)| + 4 + α.

Now

2deg(e) = 2|S ∩ Δ(e)| + 2|T ∩ Δ(e)| + 4 ≥ deg(a_{12}) + deg(b_{45})

and so |S ∩Δ(e)| ≥ α. On the other hand, α ≥ 8 and |S ∩Δ(e)| ≤ 8, whence |S ∩ Δ(e)| = α = 8.

It follows that (i) deg(e) = deg(a_{12}) = deg(b_{45}); (ii) a_{37}, a_{38}, b_{67}, b_{68} are present, and either a_{ij} or b_{ij} is present for each ij = 14, 25, 36, 78.

If both a_{14} and a_{25} are present then so are a_{36} and a_{78}, because deg(e) = deg(a_{12}) = deg(b_{45}). Similarly, if both b_{14} and b_{25} are present then so are b_{36} and b_{78}. Identical arguments hold when we apply the permutation (123)(456) to subscripts, and we conclude that either a_{ij}(ij = 14, 25, 36, 78) are present or b_{ij}(ij = 14, 25, 36, 78) are present. Moreover all of a_{12}, a_{13}, a_{23}, b_{45}, b_{46}, b_{56} have the same degree as e. It follows that there are no further vectors of type c, and no vectors of type d other than d_{4567}, d_{4568}. The 28 vectors which remain are a_{12}, b_{45}, c_{14}, c_{25}, c_{36}, d_{4567}, d_{4568}, e, the 8 vectors in S ∩ Δ(e) and the 12 vectors in T. By duality we may assume that the number of vectors of type b does not exceed the number of vectors of type a. Accordingly just one graph arises, namely the graph M002 defined in Section 1.

4. The case θ = 2

Without loss of generality, suppose that {c_{13}, c_{24}} is a largest set of pairwise orthogonal vectors of type c. In view of the incompatibilities (AC), (BC), (CC) the further possible vectors of types a, b, c in R(G) are

a_{ij}(ij = 13, 24; 12; 15, 16, 17, 18, 25, 26, 27, 28; 56, 57, 58, 67, 68, 78);
b_{ij}(ij = 13, 24; 34; 35, 36, 37, 38, 45, 46, 47, 48; 56, 57, 58, 67, 68, 78);

and

c_{ij}(ij = 14, 15, 16, 17, 18, 23, 25, 26, 27, 28, 53, 54, 63, 64, 73, 74, 83, 84).

Lemma 4.1 The vectors a_{12} and b_{34} are present.

P r o o f. If a_{12} is absent then it is excluded by a vector of type d compatible with c_{13} and c_{24}, and this is necessarily d_{1234}. Similarly, if b_{34} is absent then it is excluded by d_{5678}. Since d_{1234} and d_{5678} are incompatible at least one of a_{12}, b_{34} is present. If only a_{12} is present then d_{5678} is present and so the further possible vectors of type a or b are:

a_{ij}(ij = 13, 24, 12, 15, 16, 17, 18, 26, 26, 27, 28)

and

b_{ij}(ij = 35, 36, 37, 38, 45, 46, 47, 48; 56, 57, 58, 67, 68, 78).

Thus a_{12} is adjacent to all other neighbours of e, as well as to d_{5678} and c_{13}. Then deg(a_{12}) > deg(e), a contradiction. If only b_{34} is present then we obtain similarly the contradiction deg(b_{34}) > deg(e). Consequently both a_{12} and b_{34} are present. □

Let us now introduce some more notation: γ_{1} (resp. γ_{2}) is the number of vectors of type c adjacent to one (resp. both) of a_{12}, b_{34}, while δ_{1} (resp. δ_{2}) is the number of vectors of type d adjacent to one (resp. both) of a_{12}, b_{34}. Note that γ_{2} ≥ 2. Let

S={a_{ij}: ij = 13, 24, 56, 57, 58, 67, 68, 78} ∪ {b_{ij}: ij = 13, 24, 56, 57, 58, 67, 68, 78},

T ={a_{ij}: ij = 15, 16, 17, 18, 25, 26, 27, 28} ∪ {b_{ij} : ij = 35, 36, 37, 38, 45, 46, 47, 48}.

Lemma 4.2 With the above notation, the following holds:

γ_{1} + 2γ_{2} + δ_{1} + 2δ_{2} ≤ |S ∩ Δ(e)|.  (1)

Proof. We have

deg(a_{12}) + deg(b_{45}) = 4 + 2|S ∩ Δ(e)| + |T ∩ Δ(e)| + γ_{1} + 2γ_{2} + δ_{1} + 2δ_{2}

and

deg(e) = 2 + |S ∩ Δ(e)| + |T ∩ Δ(e)|.

The lemma follows because deg(a_{12}) + deg(b_{45}) ≤ 2deg(e). □

Lemma 4.3 At most one of the vectors c_{14} and c_{23} is present.

P r o o f. If both c_{14} and c_{23} are present then δ_{2} ≥ 4 and so |S∩Δ(e)| ≥ 8 by Lemma 4.2. On the other hand, a_{24} and b_{13} are excluded by c_{14}, while b_{24} and a_{13} are excluded by c_{23}. Thus |S ∩ Δ(e)| ≤ 6, a contradiction. □

The next three lemmas are symmetric in 5,6,7,8.

Lemma 4.4 If a_{78} and b_{56} are absent then either (a) d_{3478} is present or (b) b_{78} and a_{56} are absent. In particular, if b_{78} and a_{56} are present then d_{3478} is present.

P r o o f. The vector d_{3478} is compatible with all remaining possible vectors of type a, b or c. Accordingly if (a) does not hold then d_{3478} is excluded by some vector d_{ijkl}. Since b_{34} is present (by Lemma 4.1), it follows from (DD) and (BD) that {i, j, k, l} ∩ {3, 4, 7, 8} is {3} or {4}. In the former case, ijkl = 1356 since c_{24} excludes d_{2356}: and in the latter case, ijkl = 2456 since c_{13} excludes d_{1456}. In both cases, b_{78} and a_{56} are excluded. □

Note that the assertions of Lemmas 4.1 to 4.4 remain true of ϕ(R(G)) when we apply the permutation (13)(24) to subscripts, and this justifies the duality arguments used in the sequel.

Lemma 4.5 If a_{56} and b_{56} are absent then there exist vectors d_{ijkl} and d_{i′j′k′l′} with {5, 6} ⊆ {i, j, k, l} and {5, 6} ∩ {i′, j′, k′, l′} = ∅.

P r o o f. The vector a_{56} can be excluded by c_{15}, c_{16}, c_{25}, c_{26} or d_{ijkl} where {5, 6} ⊆ {i, j, k, l}; and b_{56} can be excluded by c_{53}, c_{54}, c_{63}, c_{64} or d_{i′j′k′l′} where {5, 6} ∩ {i′, j′, k′, l′} = ∅. By duality it suffices to exclude two possibilities: (i) each of a_{56}, b_{56} is excluded by a vector of type c, (ii) a_{56} is excluded by a vector of type c and b_{56} is excluded by a vector of type d.

In case (i) we may assume without loss of generality first that a_{56} is excluded by c_{15}, and then that b_{56} is excluded by c_{63} (since c_{15} excludes c_{53} and c_{54}). In view of (AC) and (BC) the possible vectors in S ∩ Δ(e) are a_{ij}(ij = 67, 68, 78; 13, 24) and b_{ij}(ij = 57, 58, 78; 13, 24). Note that by (AB), |S ∩ Δ(e)| ≤ 7. Since γ_{1} ≥ 2 and γ_{2} ≥ 2 we have |S ∩ Δ(e)| ≥ 6 by Lemma 4.2. Hence at most one of the vectors b_{57}, b_{58}, a_{67}, a_{68} is absent. Wihtout loss of generality, a_{67} and b_{58} are present. By Lemma 4.4, d_{3467} is present, and so δ_{2} ≥ 1. Now Lemma 4.2 yields the contradiction |S ∩ Δ(e)| ≥ 8.

In case (ii) we may suppose without loss of generality that a_{56} is excluded by c_{15} and b_{56} is excluded by d_{i′j′k′l′}. This last vector must be compatible with c_{13}, c_{24}, c_{15}, and hence is one of d_{3478}, d_{2478}, d_{2347}, d_{2348}.

Since a_{12} is adjacent to e, b_{34}, c_{13}, c_{24} and c_{15}, we know that

deg(a_{12}) ≥ 5 + |S ∩ Δ(a_{12})| + |T ∩ Δ(e)|,

while

deg(e) = 2 + |S ∩ Δ(a_{12})| + |S ∩ Δ(b_{34})| + |T ∩ Δ(e)|.

Since deg(e) ≥ deg(a_{12}), it follows that |S∩Δ(b_{34})| ≥ 3. Since S∩Δ(b_{34}) ⊆ {b_{24}, a_{67}, a_{68}, a_{78}} we conclude that not both b_{67} and b_{68} are present. If say b_{67} is absent then we may apply Lemma 4.4 to a_{58}, b_{67} to deduce that either (a) d_{3458} is present or (b) b_{58}, a_{67} are absent.

In subcase (a), |S ∩ Δ(e)| = 7 and either a_{58}, b_{57} are present or a_{68}, b_{57} are present. By Lemma 4.4 either d_{3467} or d_{3468} is present, and so δ_{2} ≥ 2. By Lemma 4.2, |S ∩ Δ(e)| ≥ 8, a contradiction. In subcase (b), |S ∩ Δ(e)| = 5, S ∩ Δ(b_{34}) = {b_{24}, a_{68}, a_{78}}, δ_{1} = 0 and δ_{2} = 0. Then d_{i′j′k′l′} = d_{2478}, a contradiction because this vector is not compatible with a_{78}. □

Lemma 4.6 If a_{56} and b_{56} are absent then so are a_{78} and b_{78}.

P r o o f. We suppose that the conclusion does not hold, and obtain a contradiction. By Lemma 4.4, either a_{78} and d_{3456} are present or b_{78} and d_{3478} are present. By duality, we may assume that the former is the case. By Lemma 4.5, a vector d_{ijkl} is present, with {5, 6} ∩ {i, j, k, l} = ∅. This vector must be compatible with a_{12} and a_{78}, and so ijkl is one of 1347,1348,2347,2348. Without loss of generality, suppose that d_{1347} is present. Now

S ∩ Δ(e) ⊆ {b_{13}, a_{24}, b_{24}, a_{57}, b_{57}, a_{58}, a_{67}, b_{67}, a_{68}, a_{78}}

and so |S ∩ Δ(a_{12})| ≤ 3. Also, in view of (AB), we have |S ∩ Δ(e)| ≤ 7. On the other hand, γ_{2} ≥ 2, δ_{1} ≥ 1 and δ_{2} ≥ 1, whence |S ∩Δ(e)| ≥ 7 by Lemma 4.2.

Next, b_{34} is adjacent to a_{12}, c_{13}, c_{24}, d_{3456}, d_{1347} and e and so

deg(b_{34}) ≥ 6 + |S ∩ Δ(b_{34})| + |T ∩ Δ(e)|.

Now, arguing as in Lemma 4.5, we obtain the contradiction |S ∩Δ(a_{12})| ≥ 4. □

We are now in a position to determine the graphs which can arise. It is convenient to discuss the various possibilites in terms of the graph Q on {5, 6, 7, 8} in which i and j are joined by a red edge if a_{ij} is present, and by a blue edge if b_{ij} is present. By duality we may assume that n_{b}(Q), the number of blue edges of Q, is not less than n_{r}(Q), the number of red edges. We distinguish five cases: (1) Q is incomplete, (2) (n_{b}(Q), n_{r}(Q)) = (6, 0),

(3) (n_{b}(Q), n_{r}(Q)) = (5, 1), (3) (n_{b}(Q), n_{r}(Q)) = (4, 2), (5) (n_{b}(Q), n_{r}(Q)) = (3, 3).

Case 1: H is incomplete.

Without loss of generality, suppose that a_{56} and b_{56} are absent. By Lemma 4.5, a vector d_{ijkl} is present, with {5, 6} ∩ {i, j, k, l} = ∅. If also {1, 2} ∩ {i, j, k, l} = ∅ then d_{ijkl} = d_{3478} and δ_{2} ≥ 2. Since also γ_{2} ≥ 2, Lemma 4.2 yields |S ∩ Δ(e)| ≥ 8, a contradiction. Since d_{ijkl} must be compatible with c_{13} and c_{24} the possibilities for ijkl are 1378, 2478.

By Lemma 4.6, a_{78} and b_{78} are absent, and so similarly either d_{1356} or d_{2456} is present. Since d_{1356} and d_{2478} are incompatible, and d_{2456} and d_{1378} are incompatible, we may assume without loss of generality that d_{2456} and d_{2478} are present. Then a_{24} and b_{13} are excluded and we note that c_{14} is compatibIe with all possible vectors of type a, b or c. It follows that c_{14} is present, for otherwise it is excluded by a vector of type d compatible with a_{12} and b_{34}: such a vector has the form d_{13uv} where {u, v} ⊆ {5, 6, 7, 8}, and is therefore not compatible with both d_{2456} and d_{2478}.

Now a_{24}, b_{13} are excluded, and we have γ_{2} ≥ 3. Since |S ∩ Δ(e)| ≤ 6 it follows from Lemma 4.2 that |S ∩ Δ(e)| = 6, γ_{2} = 3, γ_{1} = δ_{1} = δ_{2} = 0 and deg(a_{12}) = deg(b_{34}) = deg(e). In view of Lemma 4.4 (applied to nonadjacent edges of H), there are just two possibilities for S ∩ Δ(e), namely {a_{13}, a_{57}, a_{68}, b_{24}, b_{67}, b_{58}} and {a_{13}, b_{57}, b_{68}, b_{24}, a_{67}, a_{58}}.

Since γ_{2} = 3 and γ_{1} = 0 there can be no vectors of type c other than c_{13}, c_{24}, c_{14}. Moreover there are no vectors of type d other than d_{2456}, d_{2478}: the only possible vectors of type d compatible with a_{12}, b_{34}, c_{24}, d_{2456}, d_{2478} are d_{i457}, d_{i458}, d_{i467}, d_{i468}(i = 1, 2), but each of these is incompatible with both candidates for S ∩Δ(e). (For example, d_{i467} is incompatible with both b_{58} and a_{67}.)

Since d_{2456} excludes a_{25}, a_{26}, b_{37}, b_{38} and d_{2478} excludes b_{35}, b_{36}, a_{27}, a_{28}, we have

T ∩ Δ(e) = {a_{15}, a_{16}, a_{17}, a_{18}, b_{45}, b_{46}, b_{47}, b_{48}}.

By applying the permutation (56) if necessary we may assume that

S ∩ Δ(e) = {a_{13}, a_{57}, a_{68}, b_{24}, b_{58}, b_{67}}.

The vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, c_{14}, d_{2456}, d_{2478}, e together with those in S ∩ Δ(e) and T ∩ Δ(e); they are pairwise compatible and determine a maximal graph with 22 vertices. An isomorphism ψ from the resulting graph to M001 is given by:

u a_{13} c_{24} b_{34} a_{12} b_{46} b_{47} b_{45} b_{48}
ψ(u) d_{5678}a_{15} e a_{12} a_{13} a_{14} b_{67} b_{68}

u a_{17} a_{16} b_{24} c_{13} a_{57} a_{68} e a_{18} a_{15} c_{14} b_{67} b_{58} d_{2456} d_{2478} ψ(u) a_{23} a_{24} a_{34} a_{26} a_{37} a_{48} b_{56} b_{57} b_{58} b_{78} c_{15} c_{26} c_{37} c_{48} .

Here, and in isomorphisms exhibited subsequently, the first eight vectors induce a subgraph H isomorphic to E443, with degrees in H equal to 5,6,6,7,7,7,7,7.

Case 2: n_{b}(Q) = 6, n_{r}(Q) = 0.

Arguing as in Lemma 4.5, we find that |S ∩ Δ(b_{34})| ≥ 2. Since S ∩ Δ(e) contains the six vectors b_{ij}({i, j} ⊆ {5, 6, 7, 8}) it follows that

S ∩ Δ(e) = {b_{ij} : ij = 13, 24, 56, 57, 58, 67, 68, 78}.

In view of (BC) the only vectors of type c which are present are c_{13}c_{24}; and in view of (BD) there are no vectors of type d. The 29 vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, e together with those in S ∩ Δ(e) and T. They are pairwise compatible and determine a maximal graph which is the graph M428 defined in Section 1.

Case 3: n_{b}(Q) = 5, n_{r}(Q) = 1.

We may suppose that the red edge of Q is 56. Thus a_{56} and b_{78} are present, while b_{56} and a_{78} are absent. By Lemma 4.4, d_{3478} is present, and so deg(a_{12}) ≥ 5 + |S ∩ Δ(a_{12})| + |T ∩ Δ(e)|. Since deg(e) ≥ deg(a_{12}), it follows that |S ∩ Δ(b_{34})| ≥ 3, and hence that b_{13} and b_{24} are present. Since also the vectors b_{ij}(ij = 57, 58, 67, 68, 78) are present, we conclude from (BC) that c_{13}, c_{24} are the only vectors of type c present. If another vector of type d is present then it must have the form d_{ij78}(ij ≠ 34) for compatiblity with a_{56} and b_{ij}(ij = 56, 57, 67, 68, 78). However, no such vector is compatible with a_{12}, c_{13}, c_{24}, b_{13}, b_{24}. The 30 vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, d_{3478}, e together with those in S ∩ Δ(e) and T. They are pairwise compatible and determine a maximal graph which is the graph M437 defined in Section 1.

Case 4: n_{b}(Q) = 4, n_{r}(Q) = 2.

We distinguish two subcases depending on the factorization of Q induced by the edge-colouring.

Subcase 4a: The two red edges are non-adjacent.

We assume, without loss of generality, that edges 57 and 68 are red, so that S ∩ Δ(e) contains a_{57}, a_{68}, b_{56}, b_{58}, b_{67}, b_{78}. These vectors exclude all vectors of type d, and all further vectors of type c other than c_{14}, c_{23}.

By Lemma 4.3, at most one of c_{14}, c_{23} is present. If say c_{14} is present then b_{13}, a_{24} are excluded, and by maximality a_{13}, b_{24} are present. In this case the vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, c_{14}, e together with those in S ∩ Δ(e) and T. They are pairwise compatible and determine a maximal graph with 30 vertices. An isomorphism ψ from this graph to M437 is given by:

u b_{35} b_{46} a_{15} a_{12} a_{18} b_{36} a_{17} e a_{16} b_{37} b_{48} a_{25} b_{38} b_{24} a_{57}
ψ(u) a_{18} a_{25} b_{38} a_{12} a_{15} b_{36} b_{37} e a_{16} a_{17} a_{26} a_{27} a_{28} a_{56} b_{13}

u a_{68} b_{34} a_{27} a_{26} a_{28} b_{45} b_{47} b_{58} b_{78} b_{56} b_{67} a_{13} c_{13} c_{24} c_{14} ψ(u) b_{24} b_{34} b_{35} b_{45} b_{46} b_{47} b_{48} b_{57} b_{58} b_{67} b_{68} b_{78} c_{13} c_{24} d_{3478} .

If c_{14} and c_{23} are absent then c_{14} is excluded by b_{13} or a_{24}, while c_{23} is exluded by a_{13} or b_{24}. Thus either b_{13}, b_{24} are present and we obtain the graph M417 defined in Section 1; or a_{13}, a_{24} are present and an isomorphism ψ from the resulting graph to M428 is given by:

u a_{15} b_{35} b_{45} a_{12} a_{16} a_{17} a_{18} e b_{36} b_{37} b_{38} b_{46} b_{47} b_{48}
ψ(u) b_{35} a_{15} a_{25} a_{12} b_{36} b_{37} b_{38} e a_{16} a_{17} a_{18} a_{26} a_{27} a_{28}

u b_{34} a_{25} a_{26} a_{27} a_{28} b_{24} b_{13} b_{78} b_{68} b_{67} b_{58} b_{57} b_{56} c_{13} c_{24} ψ(u) b_{34} b_{45} b_{46} b_{47} b_{48} b_{13} b_{24} b_{56} b_{57} b_{58} b_{67} b_{68} b_{78} c_{13} c_{24} .

Subcase 4b: Two red edges are adjacent.

We assume, without loss of generality, that edges 56 and 67 are red, so that S ∩ Δ(e) contains a_{56}, a_{67}, b_{57}, b_{58}, b_{68}, b_{78}. By Lemma 4.4 (applied to a_{78}, b_{56} and to a_{58}, b_{67}), we know that d_{3478}, d_{3458} are present. It follows that δ_{2} ≥ 2. Since also γ_{2} ≥ 2, it follows from Lemma 4.2 that γ_{1} = δ_{1} = 0, γ_{2} = δ_{2} = 2, |S ∩ Δ(e)| = 8 and deg(a_{12}) = deg(b_{34}) = deg(e). Since deg(a_{12}) = 6 + |S ∩ Δ(a_{12})| + |T ∩ Δ(e)|, it follows that |S ∩ Δ(b_{34})| ≥ 4, and hence that b_{13} and b_{24} is present. In view of (BD) there are no further vectors of type d. The 31 vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, d_{3458}, d_{3478}, e together with those in S ∩Δ(e) and T. They are pairwise compatible and determine a maximal graph which is the graph M462 defined in Section 1.

Case 5: n_{b}(Q) = 3, n_{r}(Q) = 3.

We show first that the three red edges form a path. Otherwise thay form a star, say with edges 56, 57 and 58. By Lemma 4.4, the vectors d_{3478}, d_{3468}, d_{3467} are present. Now we have γ_{2} ≥ 2 and δ_{2} ≥ 3, contradicting Lemma 4.2.

Accordingly we assume, without loss of generality, that edges 56, 58 and 67 are red, so that S ∩ Δ(e) contains a_{56}, a_{58}, a_{67}, b_{57}, b_{68}, b_{78}. By Lemma 4.4 (applied to a_{78}, b_{56}), we know that d_{3478} is present, and so δ_{2} ≥ 1. The vectors in S ∩ Δ(e) exclude all further possible vectors of type c other than c_{14} and c_{23}.

By Lemma 4.3, at most one of c_{14}, c_{23} is present. If say c_{14} is present then b_{13}, a_{24} are excluded, and γ_{2} ≥ 3. By Lemma 4.2, we have γ_{1} = δ_{1} = 0, γ_{2} = 3, δ_{2} = 1, |S ∩ Δ(e)| = 8 and deg(a_{12}) = deg(b_{34}) = deg(e). In particular, a_{13} and b_{24} are present, but no further vectors of type c are present.

Now the only further vector of type d compatible with S∩Δ(e), a_{12}, c_{13}, c_{24} and c_{14} is d_{2478}. If this vector is present then a_{27}, a_{28}, b_{35}, b_{36} are excluded. The 28 vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, c_{14}, d_{2478}, d_{3478}, e together with the 8 vectors in S ∩ Δ(e) and the 12 vectors in T ∩ Δ(e). They are pairwise compatible and determine a maximal graph with 28 vertices. An isomorphism ψ from this graph to M002 is given by

u d_{2478}a_{12} e b_{48} a_{15} b_{78} a_{13} a_{16} b_{34} a_{67} a_{26} b_{45} c_{13} b_{37}
ψ(u) a_{14} b_{45} b_{46} a_{12} a_{13} a_{17} a_{18} e a_{23} a_{25} a_{27} a_{28} a_{36} a_{37}

u a_{18} b_{57} a_{17} b_{38} b_{47} c_{14} d_{3478} b_{24} a_{56} b_{68} c_{24} a_{58} b_{46} a_{25} ψ(u) a_{38} a_{78} b_{47} b_{48} b_{56} b_{57} b_{58} b_{67} b_{68} c_{14} c_{25} c_{36} d_{4567}d_{4568} .

If d_{2478} is absent then we obtain a maximal graph with 31 vertices, and an isomorphism ψ from this graph to M462 is given by

u b_{35} a_{15} b_{47} b_{34} a_{18} a_{16} b_{37} e b_{46} b_{48} a_{25} a_{27} a_{13} b_{78} b_{68}
ψ(u) a_{18} b_{38} b_{48} a_{12} a_{15} a_{16} a_{17} e a_{25} a_{26} a_{27} a_{28} a_{56} a_{67} b_{13}
u b_{57} a_{12} b_{38} b_{36} a_{17} a_{26} a_{28} b_{45} a_{67} a_{56} a_{58} b_{24} c_{13} c_{24} c_{14} d_{3478}
ψ(u) b_{24} b_{34} b_{35} b_{36} b_{37} b_{45} b_{46} b_{47} b_{57} b_{58} b_{68} b_{78} c_{13} c_{24} d_{3478}d_{3458} .

If c_{14} and c_{23} are absent then (arguing as above) we find that the only possible vectors of type d in addition to d_{3478} are d_{1378}, d_{2478}. If both are present then the vectors a_{ij}(ij = 27, 28, 17, 18, 24, 13) and b_{ij}(ij = 35, 36, 45, 46, 24, 13) are excluded. The vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, d_{1378}d_{2478}, d_{3478}, e together with the 6 vectors in S ∩ Δ(e) and the 8 vectors in T ∩ Δ(e). They are pairwise compatible and determine a maximal graph with 22 vertices. An isomorphism ψ from this graph to M001 is given by

u d_{3478} e b_{57} a_{16} b_{78} b_{47} b_{37} a_{12}
ψ(u) d_{5678} a_{15} e a_{12} a_{13} a_{14} b_{67} b_{68}

u b_{38} b_{34} a_{67} a_{25} b_{68} a_{58} a_{15} a_{56} b_{48} a_{26} d_{2478}c_{13} d_{1378} c_{24} ψ(u) a_{23} a_{24} a_{26} a_{34} a_{37} a_{48} b_{56} b_{57} b_{58} b_{78} c_{15} c_{26} c_{37} c_{48} .

If just one of d_{1378}, d_{2478} is present we obtain a contradiction because either c_{23} or c_{24} is then not excluded. If neither d_{1378} nor d_{2478} is present then either a_{13}, a_{24} or b_{13}, b_{24} must be present to exclude c_{14} and c_{23}. By duality we may assume that b_{13}, b_{24} are present. The vectors which remain are a_{12}, b_{34}, c_{13}, c_{24}, d_{3478}, e together with the 8 vectors in S ∩ Δ(e) and the 16 vectors in T. They are pairwise compatible and determine a maximal graph with 30 vertices. An isomorphism ψ from this graph to M437 is given by

u b_{35} a_{25} a_{15} b_{34} b_{37} b_{36} b_{38} e a_{16} a_{18} b_{48} b_{46} a_{27} b_{78} b_{68}
ψ(u) a_{18} a_{25} b_{38} a_{12} a_{15} b_{36} b_{37} e a_{16} a_{17} a_{26} a_{27} a_{28} a_{56} b_{13}

u b_{57} a_{12} a_{17} b_{45} a_{28} a_{26} b_{47} a_{67} b_{24} b_{13} a_{58} a_{56} c_{13} c_{24} d_{3478} ψ(u) b_{24} b_{34} b_{35} b_{45} b_{46} b_{47} b_{48} b_{57} b_{58} b_{67} b_{68} b_{78} c_{13} c_{24} d_{3478} .

This completes the proof of the Main Theorem formulated in Section 1.

REFERENCES

[1] A. E. B r o u w e r, A. M. C o h e n, A. N e u m a i e r, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.

[2] F. C. B u s s e m a k e r, D. C v e t k o v i ć, J. J. S e i d e l, Graphs related to exceptional root systems, T.H.-Report 76-WSK-05, Eindhoven, 1976.

[3] F. C. B u s s e m a k e r, D. C v e t k o v i ć, J. J. S e i d e l, Graphs related to exceptional root systems, in: Combinatorics (eds. A. Hajnal, V. T. Sós), North-Holland, (Amsterdam, 1978), pp. 185–191.

[4] F. C. B u s s e m a k e r, A. N e u m a i e r, Exceptional graphs with smallest eigenvalue −2 and related problems, Mathematics of Computation 59, (1992) 583–608.

[5] P. J. C a m e r o n, J. M. G o e t h a l s, J. J. S e i d e l, E. E. S h u l t, Line graphs, root systems, and elliptic geometry, J. Algebra 43, (1976) 305–327.

[6] P. J. C a m e r o n, J. H. v a n L i n t, Designs, Graphs, Codes and their Links, Cambridge University Press, Cambridge, 1991.

[7] J. H. C o n w a y, R. T. C u r t i s, S. P. N o r t o n, R. A. W i l s o n, Atlas of Finite Groups, Clarendon Press, Oxford, 1985.

[8] D. C v e t k o v i ’c, M. D o o b, H. S a c h s, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg, 1995.

[9] D. C v e t k o v i ć, M. D o o b, S. S i m i ć, Generalized line graphs, J. Graph Theory 5, (1981) 385–399.

[10] D. C v e t k o v i ć, M. L e p o v i ć, P. R o w l i n s o n, S. S i m i ć, A database of star complements of graphs, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9, (1998) 103-112.

[11] D. C v e t k o v i ć, M. L e p o v i ć, P. R o w l i n s o n, S. K. S i m i ć, The maximal exceptional graphs, to appear.

[12] D. C v e t k o v i ć, P. R o w l i n s o n, S. K. S i m i ć, Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.

[13] D. C v e t k o v i ć, P. R o w l i n s o n, S. K. S i m i ć, Some characterizations of graphs by star complements, Linear Algebra Appl. 301, (1999) 83–97.

[14] D. C v e t k o v i ć, P. R o w l i n s o n, S. K. S i m i ć, Graphs with least eigenvalue −2: the star complement technique, to appear.

[15] D. C v e t k o v i ć, P. R o w l i n s o n, S. K. S i m i ć, Constructions of the maximal exceptional graphs with largest degree less than 28, Technical Report CSM-156, Department of Computing Science and Mathematics, University of Stirling, 2000.

[16] E. R. v a n D a m, Nonregular graphs with three eigenvalues, J. Combin. Theory Ser. B 73, (1998) 101–118.

[17] P. R o w l i n s o n, Star sets and star complements in finite graphs: a spectral construction technique, in: Discrete Mathematical Chemistry (eds. P. Hansen, P. Fowler, M. Zheng), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 51, American Mathematical Society (2000), pp. 323–332.

D, Cvetković Departemnt of Mathematics Faculty of Electrical Engineering University of Belgrade P.O. Box 35-54 11120 Belgrade, Yugoslavia

P. Rowlinson Department of Computing Science and Mathematics University of Stirling Stirling FK9 4LA, Scotland

S.K. Simić Department of Mathematics Maritime Faculty Kotor 85 330 Kotor, Dobrota 36 Montenegro, Yugoslavia