TOPICS

# 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.

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

 abcilu abdfrs abejop abgmnq abhktv acdghp aceqrv acfjnt ackmos ademtu adinov adjklq aefgik aehlns afhoqu aflmpv agjsuv aglort ahijmr aipqst aknpru bcdekn bcfgov bchjqs bcmprt bdgijt bdhlmo bdpquv beflqt beghru beimsv bfhinp bfjkmu bgklps bikoqr bjlnrv bnostu cdfimq cdjoru cdlstv cefpsu cegjlm cehiot cfhklr cginrs cgkqtu chmnuv cijkpv clnopq defhjv degoqs deilpr dfglnu dfkopt dgkmrv dhiksu dhnqrt djmnps efmnor egnptv ehkmpq eijnqu ejkrst eklouv fghmst fgjpqr fijlos firtuv fknqsv ghilqv ghjkno gimopu hjlptu hoprsv iklmnt jmoqtv lmqrsu

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."

Doubly Truncated Witt Graph, Gewirtz Graph, Goethals-Seidel Graphs, Higman-Sims Graph, Integral Graph, Mathieu Groups, Strongly Regular Graph, Witt Design

## Explore with Wolfram|Alpha

More things to try:

## References

Brouwer, A. E. "M22 Graph." http://www.win.tue.nl/~aeb/drg/graphs/M22.html.Brouwer, A. E. "The Uniqueness of the Strongly Regular Graph on 77 Points." J. Graph Th. 7, 455-461, 1983.DistanceRegular.org. " Graph." http://www.distanceregular.org/graphs/m22graph.html.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

## Cite this as:

Weisstein, Eric W. "M_22 Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/M22Graph.html