Граф M22

Граф M22, называемый также графом Меснера[1][2][3], это единственный сильно регулярный граф с параметрами (77, 16, 0, 4)[4]. Граф строится из системы Штейнера (3, 6, 22), принимая его 77 блоков в качестве вершин и соединяя две вершины тогда и только тогда, когда они не имеют общих элементов. Граф можно получить также удалением вершины и её соседей из графа Хигмана — Симса[5][6].

Граф M22, Граф Меснера [1][2][3]

Граф Матьё M22, Граф Меснера
Вершин 77
Рёбер 616

Граф является одним из семи известных строго регулярных графов без треугольников[7]. Его спектр равен [5], а его группой автоморфизмов служит группа Матьё M22[4].

См. также

Литература
  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. Slide 5 list of triangle-free SRGs says "Mesner graph"
  3. Section 3.2.6 Mesner graph
  4. Andries E. Brouwer Technische Universiteit Eindhoven M22 Graph Accessed=29 May 2018.
  5. Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html. Accessed 29 May 2018.
  6. Vis, Timothy. University of Colorado Denver, The Higman–Sims Graph. Accessed 29 May 2018.
  7. Weisstein Eric W. «Strongly Regular Graph» From Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.