M₂₂ graph

There is a unique strongly regular graph Γ with parameters v = 77, k = 16, λ = 0, μ = 4. The spectrum is 16¹ 2⁵⁵ (–6)²¹. 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₂₂.2 of order 887040, acting rank 3 with point stabilizer 2⁴: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₃(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⁴:S₆ with vertex orbit sizes 1+16+60.

c) An Odd graph O₄. The Odd graph O₄ 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₇ 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⁵:S₅ 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³:L₃(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₆.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₂(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.

M22 graph