M_22 Graph

The graph, also known as the 77-graph, is a strongly regular graph on 77 nodes related to the Mathieu group and to the Witt design. It is illustrated above in an embedding with 11-fold symmetry due to T. Forbes (pers. comm., Dec. 28, 2007).

It is distance-regular with intersection array . It is also distance-transitive.

It is an integral graph with graph spectrum .

It can be obtained from the Witt design by selecting the 77 vectors of length 7 that contain a given symbol (arbitrarily chosen from 1-23) then eliminating that symbol from each of these vectors and renumbering. The resulting set of vectors gives the unique size 77 Steiner system on points 1 to 22. Now consider as vertices the 77 vectors (), with adjacent if share no terms. The resulting graph is the graph.

The graph can also be obtained by vertex deletion of the neighbors of a point in the Higman-Sims graph (but is not, as claimed by van Dam and Haemers (2003), the subgraph induced by the vertex neighbors). Also note that van Dam and Haemers (2003) refer to the doubly truncated Witt graph as , calling the 77-vertex graph the "local Higman-Sims graph."

Explicitly, the graph can be constructed by taking the following 77 words as vertices and constructing edges for each pair of vertices that have no letters in common.