Yet another distance-regular graph related to a Golay code

Leonard H. Soicher School of Mathematical Sciences Queen Mary and Westfield College Mile End Road, London E1 4NS, U.K. email: L.H.Soicher@qmw.ac.uk

Submitted: January 20, 1995; Accepted: January 22, 1995

Abstract

We describe a new distance-regular, but not distance-transitive, graph. This graph has intersection array {110, 81, 12; 1, 18, 90}, and automorphism group M_{22}: 2.

In [1], Brouwer, Cohen and Neumaier discuss many distance-regular graphs related to the famous Golay codes. In this note, we describe yet another such graph.

Ivanov, Linton, Lux, Saxl and the author [4] have classified all primitive distance-transitive representations of the sporadic simple groups and their automorphism groups. As part of this work, all multiplicity-free primitive representations of such groups have also been classified. One such representation is M_{22}: 2 on the cosets of L_{2}(11): 2. This representation has rank 6, with subdegrees 1, 55, 55, 66, 165, 330. Let Γ be the graph obtained by the edge-union of the orbital graphs corresponding to the two suborbits of length 55. By examining the sum

1991 Mathematics Subject Classification: 05E30, 05C25

( \begin{matrix}0 & 55 & 0 & 0 & 0 & 0 \\ 1 & 8 & 4 & 0 & 18 & 24 \\ 0 & 4 & 12 & 0 & 3 & 36 \\ 0 & 0 & 0 & 10 & 10 & 35 \\ 0 & 6 & 1 & 4 & 20 & 24 \\ 0 & 4 & 6 & 7 & 12 & 26 \end{matrix} ) + ( \begin{matrix}0 & 0 & 55 & 0 & 0 & 0 \\ 0 & 4 & 12 & 0 & 3 & 36 \\ 1 & 12 & 0 & 0 & 30 & 12 \\ 0 & 0 & 0 & 10 & 20 & 25 \\ 0 & 1 & 10 & 8 & 4 & 32 \\ 0 & 6 & 2 & 5 & 16 & 26 \end{matrix} )

of the intersection matrices corresponding to these two orbital graphs, we see that Γ is distance-regular, with intersection array

{110, 81, 12; 1, 18, 90}.

According to [1, p.430], this graph was previously unknown.

We now give a description of Γ in terms of a punctured binary Golay code. This description was obtained using the GRAPE share library package [7] of the GAP system [6] (available from ftp.math.rwth-aachen.de).

Let C_{22} be the code obtained by puncturing in one co-ordinate the (nonextended) binary Golay code. Then C_{22} is a [22, 12, 6]–code, with automorphism group M_{22}: 2. Let M be the set of the 77 minimum weight non-zero words of C_{22}, and V be the set of the 672 unordered pairs of words of weight 11 which have disjoint support. For v = {v_{1}, v_{2}} ∈ V define

M(v): = {m ∈ M | weight(v_{1} + m) = weight(v_{2} + m)}.

We remark that M(v) has size 55.

Now define Γ to have vertex set V, with vertices v, w joined by an edge if and only if

|M(v) ∩ M(w)| = 43.

We use GRAPE to check that Γ is indeed distance-regular, with intersection array {110, 81, 12; 1, 18, 90}. Using nauty [5] within GRAPE, we determine that Aut(Γ) ≅ M_{22}: 2, and so Γ is not distance-transitive.

Further computations reveal the following intriguing fact. Let v, w ∈ V, v ≠ w. Then in Γ, we have

d(v, w) = i

if and only if

|M(v) ∩ M(w)| = 47 − 4i.

As noted in [1, p.430], the distance-2 graph Γ_{2} is strongly regular, and it has parameters

(v, k, λ, μ) = (672, 495, 366, 360).

Indeed, Γ_{2} is a rank 3 graph for U_{6}(2) (illustrating M_{22} ≤ U_{6}(2)). The full automorphism group of Γ_{2} is U_{6}(2): S_{3}.

It would be interesting to have a natural computer-free proof of the results in this note, and to see if these results generalize to other codes.

Remark A.A. Ivanov has since informed me that about ten years ago he and his colleagues in Moscow discovered the four class association scheme associated with the graph Γ (see [2, 3]), but they did not check this scheme to determine if it came from a distance-regular graph.

References

[1] A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer, Berlin and New York, 1989.

[2] I.A. Faradzev, M.H. Klin and M.E. Muzichuk, Cellular rings and groups of automorphisms of graphs, in Investigations in Algebraic Theory of Combinatorial Objects (I.A. Faradzev, A.A. Ivanov, M.H. Klin and A.J. Woldar, eds.), Kluwer Academic Publishers, 1994, pp. 1–153.

[3] A.A. Ivanov, M.H. Klin and I.A. Faradzev, Primitive representations of nonabelian simple groups of order less than 10^{6}, Part 2, Preprint, VNIISI, Moscow, 1984.

[4] A.A. Ivanov, S.A. Linton, K. Lux, J. Saxl and L.H. Soicher, Distancetransitive representations of the sporadic groups, Comm. Algebra, to appear.

[5] B.D. McKay, nauty user’s guide (version 1.5), Technical report TR-CS-90-02, Computer Science Department, Australian National University, 1990.

[6] M. Schönert, et. al., GAP – Groups, Algorithms and Programming, fourth edition, Lehrstuhl D für Mathematik, RWTH Aachen, 1994.

[7] L.H. Soicher, GRAPE: a system for computing with graphs and groups, in Groups and Computation, L. Finkelstein and W.M. Kantor, eds., DI-MACS Series in Discrete Mathematics and Theoretical Computer Science 11, A.M.S., 1993, pp. 287–291.