M_22 Graph

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

The graph is implemented in the Wolfram Language as GraphData["M22Graph"].

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 and adjacent if they share no terms. The resulting graph is the graph.

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

The graph can also be obtained by vertex deletion of a graph vertex and all its neighbors in the Higman-Sims graph (but is not, as claimed by van Dam and Haemers (2003), the induced subgraph on the neighbors of a graph vertex). 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."