В математической области теории графов граф Холла –Янко , также известный как граф Холла–Янко–Уэйлса , представляет собой 36- регулярный неориентированный граф со 100 вершинами и 1800 рёбрами. [1]
Это сильно регулярный граф ранга 3 с параметрами (100,36,14,12) и максимальной кокликой размера 10. Этот набор параметров не является уникальным, однако он однозначно определяется своими параметрами как граф ранга 3. Граф Холла–Янко был первоначально построен Д. Уэйлсом для установления существования группы Холла–Янко как подгруппы индекса 2 ее группы автоморфизмов .
Граф Холла–Янко может быть построен из объектов в U 3 (3), простой группе порядка 6048: [2] [3]
- В U 3 (3) имеется 36 простых максимальных подгрупп порядка 168. Это вершины подграфа, графа U 3 (3). 168-подгруппа имеет 14 максимальных подгрупп порядка 24, изоморфных S 4 . Две 168-подгруппы называются смежными, если они пересекаются по 24-подгруппе. Граф U 3 (3) является сильно регулярным с параметрами (36,14,4,6)
- Имеется 63 инволюции (элементы порядка 2). 168-подгруппа содержит 21 инволюцию, которые определяются как соседи.
- Пусть снаружи U3 ( 3) находится 100-я вершина C , соседями которой являются 36 168-подгрупп. Тогда 168-подгруппа имеет 14 общих соседей с C и всего 1+14+21 соседей.
- Инволюция обнаружена в 12 из 168 подгрупп. C и инволюция несмежны, имеют 12 общих соседей.
- Две инволюции определяются как смежные, если они порождают диэдральную подгруппу порядка 8. [4] Инволюция имеет 24 инволюции в качестве соседей.
Характеристический многочлен графа Холла–Янко равен . Поэтому граф Холла–Янко является целочисленным графом : его спектр состоит исключительно из целых чисел.
Ссылки
- ^ Вайсштейн, Эрик В. «График Холла-Янко». Математический мир .
- ^ Андрис Э. Брауэр, «График Холла-Янко».
- ^ Андрис Э. Брауэр, «Граф U3(3)».
- ^ Роберт А. Уилсон, «Конечные простые группы», Springer-Verlag (2009), стр. 224.