The M22 graph, also called the Mesner graph[1][2][3] or Witt graph[4] is the unique strongly regular graph with parameters (77, 16, 0, 4).[5] It is constructed from the Steiner system (3, 6, 22) by representing its 77 blocks as vertices and joining two vertices iff they have no terms in common or by deleting a vertex and its neighbors from the Higman–Sims graph.[6][7]
| M22 graph, Mesner graph[1][2][3] | |
|---|---|
 | |
| Named after | Mathieu group M22, Dale M. Mesner |
| Vertices | 77 |
| Edges | 616 |
| Table of graphs and parameters | |
For any term, the family of blocks that contain that term forms an independent set in this graph, with 21 vertices. In a result analogous to the Erdős–Ko–Rado theorem (which can be formulated in terms of independent sets in Kneser graphs), these are the unique maximum independent sets in this graph.[4]
It is one of seven known triangle-free strongly regular graphs.[8] Its graph spectrum is (−6)21255161,[6] and its automorphism group is the Mathieu group M22.[5]
See also
editReferences
edit- ^ a b "Mesner graph with parameters (77,16,0,4). The automorphism group is of order 887040 and is isomorphic to the stabilizer of a point in the automorphism group of NL2(10)"
- ^ a b Slide 5 list of triangle-free SRGs says "Mesner graph"
- ^ a b Section 3.2.6 Mesner graph
- ^ a b Godsil, Christopher; Meagher, Karen (2015), "Section 5.4: The Witt graph", Erdős–Ko–Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, Cambridge University Press, pp. 94–96, ISBN 9781107128446
- ^ a b Brouwer, Andries E. “M22 Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. Accessed 29 May 2018.
- ^ a b Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html. Accessed 29 May 2018.
- ^ Vis, Timothy. “The Higman–Sims Graph.” University of Colorado Denver, http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf. Accessed 29 May 2018.
- ^ Weisstein, Eric W. “Strongly Regular Graph.” From Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html.