Up

# M22 graph

There is a unique strongly regular graph Γ with parameters v = 77, k = 16, λ = 0, μ = 4. The spectrum is 161 255 (–6)21. Construction is folklore. An early reference is Mesner (1964). Uniqueness was proved by Brouwer (1983).

## Construction

The graph is the block graph of the Steiner system S(3,6,22), where blocks are called adjacent when they are disjoint. It is strongly regular because this design is quasi-symmetric: block intersections have size 0 or 2.

## Group

Its automorphism group is M22.2 of order 887040, acting rank 3 with point stabilizer 24:Sym(6).

## Supergraphs

The graph is the subgraph of the Higman-Sims graph induced on the set of vertices at distance 2 from a given vertex.

## Subgraphs

a) A 21-coclique or Gewirtz graph There are 22 cocliques of size 21, forming a single orbit. (In the S(3,6,22) description these are the 22 symbols. In the Higman-Sims graph these are neighbourhoods of the points outside the 77.) The stabilizer of one is L3(4).2 with vertex orbit sizes 21+56. The subgraph induced on the 56 is the Gewirtz graph. Two 21-cocliques meet in 5 points, so a 21-coclique and a Gewirtz subgraph meet in 0 or 16 points.

Concerning cocliques of other sizes: Γ has maximal cocliques of the following sizes:

```size number
7: 330
10: 216832
11: 149184
13: 43120
14: 330
16: 1309
21: 22
```

b) A vertex. There are 77 of these, forming a single orbit. The stabilizer of one is 24:S6 with vertex orbit sizes 1+16+60.

c) An Odd graph O4. The Odd graph O4 is the graph on the disjoint triples in a 7-set. There are 352 of these, forming a single orbit. The stabilizer of one is A7 with vertex orbit sizes 35+42. The subgraph induced on the 42 is the second subconstituent of the Hoffman-Singleton graph. In the Steiner system S(5,8,24), let a and b be two fixed symbols, such that our S(3,6,22) is the derived design at {a,b}. Our 352 things are the 352 octads that contain precisely one of a,b.

d) A pair of 21-cocliques. There are 231 of these, forming a single orbit. The stabilizer of one is 25:S5 with vertex orbit sizes 5+32+40. The subgraph induced on the 32 is the folded 6-cube.

e) Maximal 7-cocliques. There are 330 of these, forming a single orbit. The stabilizer of one is 23:L3(2)×2 with vertex orbit sizes 7+56+14. The subgraphs induced on the 7 and the 14 are the maximal 7- and 14-cocliques. In the Steiner system S(5,8,24), let a and b be two fixed symbols, such that our S(3,6,22) is the derived design at {a,b}. Our 330 things are the 330 octads that contain neither a nor b, and the orbits of size 7,56,14 correspond to intersection size 0,2,4.

f) An edge. There are 616 of these, forming a single orbit. The stabilizer of one is A6.22 with vertex orbit sizes 2+30+45. The subgraph induced on the 30 is the point-line incidence graph of the generalized quadrangle GQ(2,2). The subgraph induced on the 45 is the distance-2 graph of the unique distance-regular graph with intersection array {4,2,2,2;1,1,1,2}, the generalized octagon GO(2,1), the flag graph of GQ(2,2).

g) Incidence graph of complement of biplane on 11 points. The unique biplane on 11 points has parameters 2-(11,5,2). The complementary design is a 2-(11,6,3), with incidence graph that is distance regular with intersection array {6,5,3;1,3,6}. There are 672 of these, forming a single orbit. The stabilizer of one is L2(11):2 with vertex orbit sizes 22+55.

## Chromatic number

The chromatic number is 5. (If no 21-coclique is used as a colour then at least 77/16 colours are needed. If a 21-coclique is used, then what is left is the Gewirtz graph, and that has chromatic number 4.)

## Cycles

This graph is Hamiltonian.

## References

A.E. Brouwer, The uniqueness of the strongly regular graph on 77 points, J. Graph Th. 7 (1983) 455-461.

D.M. Mesner, Negative Latin square designs, Institute of Statistics, UNC, NC Mimeo series 410, November 1964.