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

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

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

Граф Хоффмана — Синглтона. Подграф с синими рёбрами является суммой десяти непересекающихся пентагонов.

Построение

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

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

Возьмём 5 пятиугольников $P_{h}$ и 5 пентаграмм $Q_{i}$ так, что вершина $j$ пятиугольника $P_{h}$ смежна вершинам $j-1$ и $j+1$ пятиугольника $P_{h}$ и вершина $j$ пентаграммы $Q_{i}$ смежна вершинам $j-2$ и $j+2$ пентаграммы $Q_{i}$ . Свяжем вершину $j$ графа $P_{h}$ с вершиной $h\bullet {i}+j$ графа $Q_{i}$ . (Все индексы берутся по модулю 5.)

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

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

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

Группа автоморфизмов графа Хоффмана — Синглтона является группой порядка 252000 и изоморфна PΣU(3,5²), полупрямому произведению проективной специальной унитарной группы $PSU(3,5^{2})$ и циклической группы порядка 2, сгенерировнной эндоморфизмом Фробениуса. Автоморфизм действует транзитивно на вершины и рёбра графа. Таким образом, граф Хоффмана — Синглтона является симметричным графом. Стабилизатор вершин графа изоморфен симметрической группе $S_{7}$ на 7 буквах. Стабилизатор множества рёбер изоморфен $Aut(A_{6})=A_{6}\cdot 2^{2}$ , где $A_{6}$ — знакопеременная группа на 6 буквах. Оба типа стабилизаторов являются максимальными подгруппами полной группы автоморфизмов графа Хоффмана — Синглтона.

Характеристический многочлен графа Хоффмана — Синглтона равен $(x-7)(x-2)^{28}(x+3)^{21}$ . Таким образом, граф Хоффмана — Синглтона является целочисленным — его спектр состоит полностью из целых чисел.

Подграфы

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

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

См. также

Таблица наибольших известных графов заданного диаметра и максимальной степени

Примечания

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

Литература

P. R. Hafner. The Hoffman-Singleton Graph and Its Automorphisms // J. Algebraic Combin. — 2003. — Т. 18.
G. Royle. Re: What is the Edge Chromatic Number of Hoffman-Singleton? (неопр.). GRAPHNET@istserv.nodak.edu posting. (Sept. 28, 2004.). (недоступная ссылка)
M.D.E. Conder, K. Stokes. Minimum genus embeddings of the Hoffman-Singleton graph // preprint. — 2014.
C. T. Benson, N. E. Losey. On a graph of Hoffman and Singleton // Journal of Combinatorial Theory. Series B. — Т. 11, вып. 1. — С. 67–79. — ISSN 0095-8956. — doi:10.1016/0095-8956(71)90015-3.
D.A. Holton, J. Sheehan. The Petersen graph. — Cambridge University Press, 1993. — С. 186, 190. — ISBN 0-521-43594-3..
Andries E. Brouwer. Hoffman-Singleton graph (неопр.).
Alan J. Hoffman, Robert R. Singleton. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. — 1960. — Т. 5, вып. 4. — С. 497–504. — doi:10.1147/rd.45.0497.
Pak-Ken Wong. On the uniqueness of the smallest graph of girth 5 and valency 6 // Journal of Graph Theory. — 1979. — Т. 3. — С. 407–409. — doi:10.1002/jgt.3190030413.

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

[MW-1] Weisstein, Eric W. Hoffman-Singleton Graph (англ.) на сайте Wolfram MathWorld.

[_83522b0507f8d81d-2] Hafner, 2003, с. 7-12.

[_524de1843aaaccf2-3] Royle.

[_d10095ab081e18aa-4] Conder, Stokes, 2014.

[_e607c440d0d63139-5] Brouwer.

[_04cdf7a143bc22b5-6] Hoffman, Singleton, 1960, с. 497–504.

[_dd8800cd52adbd1f-7] Wong, 1979, с. 407–409.