Граф M22 (Ijgs M22)

Перейти к навигации Перейти к поиску
Граф M22, Граф Меснера [1][2][3]
Граф Матьё M22[англ.], Граф Меснера
Граф Матьё M22[англ.], Граф Меснера
Вершин 77
Рёбер 616

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

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

Литература

[править | править код]
  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)". Дата обращения: 30 января 2019. Архивировано 1 мая 2018 года.
  2. 1 2 Slide 5 list of triangle-free SRGs says "Mesner graph". Дата обращения: 30 января 2019. Архивировано 15 ноября 2018 года.
  3. 1 2 Section 3.2.6 Mesner graph. Дата обращения: 30 января 2019. Архивировано 15 ноября 2018 года.
  4. 1 2 Andries E. Brouwer Technische Universiteit Eindhoven M22 Graph Архивная копия от 18 февраля 2019 на Wayback Machine Accessed=29 May 2018.
  5. 1 2 Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html Архивная копия от 18 февраля 2019 на Wayback Machine. Accessed 29 May 2018.
  6. Vis, Timothy. University of Colorado Denver, The Higman–Sims Graph Архивная копия от 24 июля 2010 на Wayback Machine. Accessed 29 May 2018.
  7. Weisstein Eric W. «Strongly Regular Graph» From Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html