М 22 график
| График М 22 , график Меснера [1] [2] [3] | |
|---|---|
 | |
| Названный в честь | Группа Матье М 22 , Дейл М. Меснер |
| Вершины | 77 |
| Края | 616 |
| Таблица графиков и параметров | |
Граф М 22 , также называемый графом Мезнера [1] [2] [3] или график Витта [4] — единственный сильно регулярный граф с параметрами (77, 16, 0, 4). [5] Он строится на основе системы Штейнера (3, 6, 22) путем представления ее 77 блоков в виде вершин и соединения двух вершин, если они не имеют общих членов, или путем удаления вершины и ее соседей из графа Хигмана – Симса . [6] [7]
Для любого термина семейство блоков, содержащих этот термин, образует независимое множество в этом графе с 21 вершиной. В результате, аналогичном теореме Эрдеша–Ко–Радо (которая может быть сформулирована в терминах независимых множеств в графах Кнезера ), это уникальные максимальные независимые множества в этом графе. [4]
Это один из семи известных сильно регулярных графов без треугольников . [8] Спектр его графика равен (−6) 21 2 55 16 1 , [6] а ее группой автоморфизмов является группа Матье M22 . [5]
См. также [ править ]
Ссылки [ править ]
- ^ Перейти обратно: а б «Граф Меснера с параметрами (77,16,0,4). Группа автоморфизмов имеет порядок 887040 и изоморфна стабилизатору точки в группе автоморфизмов NL2 (10)»
- ^ Перейти обратно: а б На слайде 5 в списке SRG без треугольников написано «граф Меснера».
- ^ Перейти обратно: а б Раздел 3.2.6 График Меснера
- ^ Перейти обратно: а б Годсил, Кристофер ; Мигер, Карен (2015), «Раздел 5.4: Граф Витта», Теоремы Эрдеша – Ко – Радо: алгебраические подходы , Кембриджские исследования по высшей математике, Cambridge University Press, стр. 94–96, ISBN 9781107128446
- ^ Перейти обратно: а б Брауэр, Андриес Э. «График М 22 ». Эйндховенский технологический университет , http://www.win.tue.nl/~aeb/graphs/M22.html . По состоянию на 29 мая 2018 г.
- ^ Перейти обратно: а б Вайсштейн, Эрик В. «График M22». MathWorld, http://mathworld.wolfram.com/M22Graph.html . По состоянию на 29 мая 2018 г.
- ^ Вис, Тимоти. «График Хигмана-Симса». Университет Колорадо, Денвер, http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf . По состоянию на 29 мая 2018 г.
- ^ Вайсштейн, Эрик В. «Строго регулярный граф». Из Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html.