M22 graph
| M22 graph, Mesner graph[1][2][3] | |
|---|---|
 | |
| Named after | Mathieu group M22, Dale M. Mesner |
| Vertices | 77 |
| Edges | 616 |
| Table of graphs and parameters | |
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]
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
References
- ↑ 1.0 1.1 "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)"
- ↑ 2.0 2.1 Slide 5 list of triangle-free SRGs says "Mesner graph"
- ↑ 3.0 3.1 Section 3.2.6 Mesner graph
- ↑ 4.0 4.1 "Section 5.4: The Witt graph", Erdős–Ko–Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2015, pp. 94–96, ISBN 9781107128446, https://www.cambridge.org/ht/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/erdoskorado-theorems-algebraic-approaches
- ↑ 5.0 5.1 Brouwer, Andries E. “M22 Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. Accessed 29 May 2018.
- ↑ 6.0 6.1 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.
External links
 |  |
