M22 graph

Last updated
M22 graph, Mesner graph [1] [2] [3]
M22 graph.svg
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 or Witt graph, [1] [2] [3] [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]

Contents

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. 1 2 "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. 1 2 Slide 5 list of triangle-free SRGs says "Mesner graph"
  3. 1 2 Section 3.2.6 Mesner graph
  4. 1 2 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
  5. 1 2 Brouwer, Andries E. “M22 Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. Accessed 29 May 2018.
  6. 1 2 Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html. Accessed 29 May 2018.
  7. ↑ Vis, Timothy. “The Higman–Sims Graph.” University of Colorado Denver, http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf. Accessed 29 May 2018.
  8. ↑ Weisstein, Eric W. “Strongly Regular Graph.” From Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.