Граф Хоффмана — Синглтона

Граф Хоффмана — Синглтона — 7-однородный неориентированный граф с 50 вершинами и 175 рёбрами. Граф является единственным сильно регулярным графом с параметрами [5]. Граф был построен Аланом Хоффманом и Робертом Синглтоном, когда они пытались классифицировать все графы Мура, и он является графом Мура с наибольшим порядком, для которого известно, что такой граф существует[6]. Поскольку граф является графом Мура, в котором каждая вершина имеет степень 7, а обхват графа равен 5, граф является клеткой .

граф Хоффмана – Синглтона
Назван в честь Алан Хоффман
Роберт Р. Синглтон
Вершин 50
Рёбер 175
Радиус 2
Диаметр 2[1]
Обхват 5[1]
Автоморфизмы 252,000
(PSU(3,52):2) [2]
Хроматическое число 4
Хроматический индекс 7 [3]
Род 29 [4]
Свойства Сильно регулярный
Симметричный
Гамильтонов
Целочисленный
Клетка
Граф Мура
 Медиафайлы на Викискладе
Граф Хоффмана — Синглтона. Подграф с синими рёбрами является суммой десяти непересекающихся пентагонов.

Построение

Существует много путей построения графов Хоффмана — Синглтона.

Построение на основе пятиугольников и пентаграмм

Возьмём 5 пятиугольников и 5 пентаграмм так, что вершина пятиугольника смежна вершинам и пятиугольника и вершина пентаграммы смежна вершинам и пентаграммы . Свяжем вершину графа с вершиной графа . (Все индексы берутся по модулю 5.)

Построение из троек и плоскостей Фано

Возьмём плоскость Фано и рассмотрим переставки её 7 точек, чтобы получить 30 плоскостей Фано. Выберем одну из этих плоскостей. Имеется 14 других плоскостей Фано, имеющих в точности одну общую тройку («прямую») с выбранной плоскостью. Возьмём эти 15 плоскостей Фано и отбросим оставшиеся 15. Рассмотрим 7C3 = 35 троек из 7 чисел. Теперь соединим (ребром) тройку с плоскостями Фано, содержащими эту тройку, а также соединим непересекающиеся тройки друг с другом. Получившийся граф является графом Хоффмана — Синглтона, он состоит из 50 вершин, соответствующих 35 тройкам и 15 плоскостям Фано, и каждая вершина имеет степень 7. Вершины, соответствующие плоскостям Фано, соединены с 7 тройками по определению, поскольку плоскость Фано имеет 7 прямых. Каждая тройка связана с 3 различными плоскостями Фано, включающими её, и с 4 другими тройками, с которыми она не пересекается.

Алгебраические свойства

Группа автоморфизмов графа Хоффмана — Синглтона является группой порядка 252000 и изоморфна PΣU(3,52), полупрямому произведению проективной специальной унитарной группы и циклической группы порядка 2, сгенерировнной эндоморфизмом Фробениуса. Автоморфизм действует транзитивно на вершины и рёбра графа. Таким образом, граф Хоффмана — Синглтона является симметричным графом. Стабилизатор вершин графа изоморфен симметрической группе на 7 буквах. Стабилизатор множества рёбер изоморфен , где  — знакопеременная группа на 6 буквах. Оба типа стабилизаторов являются максимальными подгруппами полной группы автоморфизмов графа Хоффмана — Синглтона.

Характеристический многочлен графа Хоффмана — Синглтона равен . Таким образом, граф Хоффмана — Синглтона является целочисленным — его спектр состоит полностью из целых чисел.

Подграфы

Используя только факт, что граф Хоффмана — Синглтона является строго регулярным с параметрами , можно показать, что в нём существует 1260 циклов длины 5.

Кроме того, граф Хоффмана — Синглтона содержит 525 копий графа Петерсена. Удаление одного из них даёт копию единственной -клетки[7].

См. также

Примечания

  1. Weisstein, Eric W. Hoffman-Singleton Graph (англ.) на сайте Wolfram MathWorld.
  2. Hafner, 2003, с. 7-12.
  3. Royle.
  4. Conder, Stokes, 2014.
  5. Brouwer.
  6. Hoffman, Singleton, 1960, с. 497–504.
  7. Wong, 1979, с. 407–409.

Литература

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