Up
# M_{22} graph

There is a unique strongly regular graph Γ with parameters
*v* = 77, *k* = 16, λ = 0, μ = 4.
The spectrum is 16^{1} 2^{55} (–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 M_{22}.2 of order 887040,
acting rank 3 with point stabilizer 2^{4}: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 L_{3}(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 2^{4}:S_{6}
with vertex orbit sizes 1+16+60.

c) *An Odd graph O*_{4}.
The Odd graph O_{4} 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 A_{7} 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 2^{5}:S_{5}
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 2^{3}:L_{3}(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 A_{6}.2^{2}
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 L_{2}(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.