Does Exist A Distance-Regular Graph with IntersectionArray

A Distance-Regular Graph with Intersection Array (5, 4, 3, 3; 1, 1, 1, 2) Does Not Exist

D.G. FON-DER-FLAASS

Institute of Mathematics, Novosibirsk-90, Russia 630090 Received May 12, 1992; Revised October 6, 1992

Abstract. We prove that a distance-regular graph with intersection array (5, 4, 3, 3; 1, 1, 1, 2) does not exist. The proof is purely combinatorial and computer-free.

Keywords: distance-regular graph, intersection array

The problem of deciding whether a distance-regular graph with a given intersec- tion array does exist is a very hard one, and far from solution. There are some necessary conditions ruling out unfeasible arrays, but vast numbers of arrays are left, for which there are no proofs either of existence or of nonexistence of corresponding graphs.

In a previous paper [2] we proved by a rather simple ad hoc argument that a distance-regular graph with the intersection array (5, 4, 3; 1, 1, 2) does not exist.

The approach used there turned out to be applicable in yet another situation, namely, for the intersection array mentioned in the title.

The excellent monograph [1] may be recommended as an introduction to the theory of distance-regular graphs. But in this paper we shall need only the basic definition.

Definition. A distance-regular graph with the intersection array (b0, b1,...,bd-1; c1, C2, ..., cd) is a b0-regular graph G of diameter d such that for every pair u, v of its vertices the following condition is satisfied:

if d(u, v) = i, then exactly bi neighbors of v are at a distance i + 1 from u; and exactly Ci ones are at a distance i - 1 from u.

THEOREM. A distance-regular graph with intersection array (5, 4, 3, 3; 1, 1, 1, 2) does not exist.

The remainder of the paper is devoted to the proof of this theorem. From now on, we suppose that G is a distance-regular graph with the specified intersection array.

Gi(v) — the set of vertices at a distance i from v.

G<i(v) = the set of vertices at a distance at most i from v.

An m-cycle or m-path is a cycle or path of length m.

Some of basic properties of G are collected in Lemma 1.

LEMMA 1.

(a) For each vertex v, there are exactly 5, 20, 60, and 90 vertices at distance 1, 2, 3, and 4 from v.

(b) G induces matchings on G2(V) and on G3(v).

(c) Any two vertices at a distance 2 or 3 are connected by exactly one path of length 3.

(d) There are no cycles of length 3, 4, 6, or 7.

(e) Any two vertices at a distance 4 are connected by exactly two 4-paths.

Proof. The diagram below represents distribution of vertices and edges of G relatively to a vertex v.

The properties (a), (b), (c), and (e) follow immediately from the diagram; the absence of 3-, 4-, and 6-cycles is also obvious. Let vv1 v2 v3 v4 v5 v6 be a cycle of length 7. It is clear that the vertices v3 and v4 should be in G3(v). By (c), the vertices v1 and v3 are connected by a unique 3-path, and, looking at the diagram, we see that it should pass through v4 and v5. So, v6 = v1, and there are no 7-cycles in G. D Next we shall determine uniquely the structure of the graph induced on G<3(v) for every vertex v.

Let I = {1, 2, 3, 4, 5}. From now on, whenever symbols i, j, k, l occur in a statement, they represent distinct elements of I.

LEMMA 2. For every vertex o e G, vertices of the graph N = G<3(0) can be labelled by the following symbols:

so that all edges of N are as follows:

Proof. Let o be any vertex of G. Label its neighbors arbitrarily by the symbols 1, 2, 3, 4, 5. Any two of them, say i and j, are at a distance 2, and so should be connected by a unique 3-path i — x — y — j. The vertices x and y are in G

(o). Label them by ij and ji, respectively. Each vertex of G

(o) gets at most one label, and since there are 20 vertices and 20 labels, we have labels for all vertices of G

(o). All edges inside G

(o) are also defined; they are of the form ij — ji. Similarly, there exists a unique 3-path ij — x — y — ik for any choice of different i, j, k. Now x and y are in G

(o), and we assign to them labels ijk and ikj, respectively. Again, we have 60 labels and 60 vertices. The lemma follows. D Now we turn to vertices in G

(o). Each one of them is adjacent to two vertices in G

(o), and is uniquely determined by them (since there are no 4-cycles). Let abc: def denote the vertex in G

(o) adjacent to abc and def (if it exists). Note that def : abc is another label for the same vertex.

By a pattern we shall mean a label in which some digits are replaced by the symbol *. A pattern defines the set of vertices, labels of which are obtained by replacing all stars by some digits.

LEMMA 3. Of 90 vertices in G

(o), there are 60 having labels of the pattern ij* : kl*, where i, j, k, l are all different; and 30 with labels of the pattern ij*: ji*.

Each of the patterns ijk : ji*, ijk : l**, ij* : kl* defines exactly one vertex.

Proof. Let us consider the vertices ijk and ji. We have d(ijk, ji) = 2, so they are joined by a unique 3-path. It should look like ji — ji* — v — ijk for some vertex v e G

(o). This vertex will be the only one defined by the pattern ijk : ji*.

Similarly, we have d(ijk, l) = 4. One of the two 4-paths between them is ijk — ij — i — o — l; the other should be

for some v e G

(o); and v is the only vertex defined by the pattern ijk : l**.

Considering, at last, vertices ij and kl, we find in the same way a unique

vertex corresponding to ij* : kl*.

We will call vertices ij* : kl* good. (The cause for this will be seen later).

Every vertex in G3(o) has exactly two good neighbors.

LEMMA 4. If G contains a vertex axy : bzt, then it cannot contain any of the vertices (a) ayx : btz; (b) ayx : bzt'; and (c) axy : zbt'.

Proof. Let v = axy : bzt, and w be one of the vertices (a), (b), (c). Then the following cycles contradict Lemma 1(d):

for some uniquely determined permutation a, b, c of the set I' = I\{i, j}.

Proof. By Lemma 3, there are six vertices determined by patterns ixy : j** for x, y e I'. Since there are 60 good vertices, and 10 unordered pairs {i, j}, each pattern i** : j** defines six good vertices with labels ixsys : jzsts, 1 < 8 <6, and any ordered pair of elements of I' is met exactly once among x^sy^s, and once among zsts. We define an auxiliary graph with the vertex set S = {1, 2, 3, 4, 5, 6}

and edges of four sorts: blue (simple or double) and red (simple or double). The rules for drawing edges are as follows.

s and s' are joined by:

A simple blue edge, iff x, = ys' and xs' = ys. A double blue edge, iff xs = xs.

A simple red edge, iff zs = ts' and zs' = ts. A double red edge, iff z^s = z^s.

We claim that each pair of vertices is joined by at most one edge. Indeed, if s and s' are joined by simple blue and simple red edges, then the corresponding vertices contradict Lemma 4(a); if they are joined by one simple edge and one double edge, then they contradict Lemma 4(b); and if they are joined by two double edges, then there are two vertices of the form ix* : jz* contradicting Lemma 3.

LEMMA 5. The pattern i** : j** defines exactly six good vertices. They have labels

Figure 1. Vertices i** : j**.

Edges of each sort form a matching; edges of each color form a 6-cycle. It's an easy exercise to verify that, up to isomorphism, there is only one possible way to draw such a configuration; it is presented on the Figure 1. Reading out from the picture labels of the vertices (this can be done in a unique way), we get the desired result. D We will use the shorthand notation ij —> abc meaning that G contains the six vertices mentioned in Lemma 5.

To determine labels of all good vertices in G4(o) we need to define 20 relations of the form ij -» abc. It turns out that we can do this uniquely up to isomorphism.

From now on, a, 6, c, d, e is an arbitrary permutation of elements of I.

LEMMA 6.

(a) If ab —» cde, then ba —> dec,

(b) If ab -» cde, then ab' -> c'd'e cannot hold for b' = b.

Proof.

(a) These two relations define the same set of vertices.

(b) If this were the case, then G would contain vertices aex : bb'* and aex : b'b*, contrary to Lemma 4(c). D

LEMMA 7. The graph G induces a matching on good vertices of the pattern

ab* : ***.

form a matching; it follows that so do the rest. D LEMMA 8. Let ab -> cde. Then

(a) The matching induced on the vertices ae* : * * * is the following:

The labels of last two vertices are given by ab —> cde .

Let's define values of xi. By Lemma 3, {x1, x2} = {b, d} and {x3, x4} = {b, c}.

By Lemma 4(c), x1 = d and x3 = c. So, x1 = b, X2 = d, x3 = b, x4 = c.

By Lemma 7, G induces on X a matching. We can determine it uniquely.

Indeed, the vertex us can be adjacent only to V4; other choices lead to cycles contradicting Lemma 1(d). For instance.

(b) Either ad —» ecb, or ad —> ebc.

Proof. Consider the set X of all good vertices of the form ae* : ***. Its elements are

Then we find similarly that v3 is adjacent to v2 and v6 to v1, and the assertion (a) is proved.

The value of y3 is c or e. If y3 = c, then we have the 7-cycle

Hence, y3 = e.

If y4 = b, then there are three 4-paths from v4 to bd:

contradicting Lemma 1(e). Hence, y⁴ = e.

So, there are vertices aeb: dbe and aec: dce. Now the assertion (b) follows from Lemma 5. D LEMMA 9. If ab —> cde, then all relations xy -> pqr are determined uniquely. They are shown in Table 1.

Table 1. Relations xy -» pqr.

a b c d e

a xxx

edc deb bce cbd

b cde xxx ead aec dca

c bed dae

xxx

eba adb

d ecb cea a be xxx

bac e dbc acd bda cab

xxx

Proof. Lemma 6(b) implies that in each row of the table all last symbols of triples are different. Moreover, all second symbols in each row are also different.

Indeed, if xy1 —» p1qr1 and xy2 -> P2qr2, then by Lemma 8(b) we have xq —» r1**

and xq —» r2**, but r1 = r2. Further, since in the ith row all symbols but i appear exactly three times, all first symbols in each row are also different. By Lemma 6(a), the same statements hold for columns.

We start with the blank table, fill in the cells (a, b) and (b, a) by triples cde and edc accordingly, and try to continue. Lemma 8(b) gives two possibilities to fill the cell (a, d): either ecb or ebc. Let's try the second one (see Table 2).

Table 2.

a b c d e

a xxx

edc cbe

b cde xxx eae

c

xxx d ebc cae xxx

e

xxx

The cell (b, d) is filled by either cae or ceo (Lemma 8(b) applied to ba —> edc).

So, the cell (d, b) is filled by either eac or aec. But aec is impossible; otherwise Lemma 8(b) would give us a relation de —» c**, contrary to da —» cbe. Hence, the cells (b, d) and (d, b) are filled as in Table 2. But then the second symbols in (c, a) and (c, b) should both be equal to e: a contradiction.

Hence, the second possibility in Lemma 8(b) never holds, and each relation xy —» pqr implies xq -» rpy. This follows from the fact that the relation ab —> cde

Now the final contradiction is near. Without loss of generality let us assume that 12 —» 345. Then Lemma 9 gives us labels of all good vertices, and Lemma 8(a) gives some edges between them. Applying Lemma 8(a) consecutively to relations

1. We have proved, in fact, a stronger result than the theorem. Since only properties of the graph G listed in Lemma 1 were used in the proof, we proved nonexistence of graphs which locally look like

around every vertex.

2. The proof presented is computer-free, but I think it would not be possible to find it without the help of a computer. In fact, after Lemma 6 was proved, a simple computer search gave 20 nonisomorphic variants for the set of relations ij -> abc. The rest of the argument appeared through many attempts to kill these variants.

References

1. A.E. Brouwer, A.M. Cohen, and A. Neumaier. Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.

2. D.G. Fon-Der-Flaass. "There exists no distance-regular graph with intersection array (5, 4, 3; 1, 1, 2)." to appear in Europ. J. Combinatorics.

we find the 4-path

which, together with vertices 132 and 123, gives us a 7-cycle, contrary to Lem- ma 1(d). The theorem is proved.

Concluding remarks