В математической области теории графов , то граф Hoffman-Singleton является 7- регулярного неориентированного графа с 50 вершинами и 175 ребер. Это единственный сильно регулярный граф с параметрами (50,7,0,1). [5] Он был построен Аланом Хоффманом и Робертом Синглтоном, пытаясь классифицировать все графы Мура , и является графом Мура самого высокого порядка, который, как известно, существует. [6] Поскольку это граф Мура, в котором каждая вершина имеет степень 7, а обхват равен 5, это (7,5) -клетка .
Граф Хоффмана – Синглтона | |
---|---|
Названный в честь | Алан Дж. Хоффман Роберт Р. Синглтон |
Вершины | 50 |
Края | 175 |
Радиус | 2 |
Диаметр | 2 [1] |
Обхват | 5 [1] |
Автоморфизмы | 252 000 ( PSU (3,5 2 ): 2) [2] |
Хроматическое число | 4 |
Хроматический индекс | 7 [3] |
Род | 29 [4] |
Характеристики | Сильно регулярный симметричный гамильтонов интегральный граф Кейджа Мура |
Таблица графиков и параметров |
Строительство
Вот две конструкции графа Хоффмана – Синглтона. [7]
Построение из пятиугольников и пентаграмм
Возьмем пять пятиугольников P h и пять пентаграмм Q i . Соедините вершину j из P h с вершиной h · i + j из Q i . (Все индексы даны по модулю 5.) [7]
Конструкция из ПГ (3,2)
Возьмите плоскость Фано на семи элементах, таких как { abc, ade, afg, bef, bdg, cdf, ceg }, и примените все 2520 четных перестановок к семи элементам abcdefg . Канонизируйте каждую такую плоскость Фано (например, уменьшив ее до лексикографического порядка) и удалите дубликаты. Осталось ровно 15 самолетов Фано. Каждый 3-набор (тройка) множества abcdefg присутствует ровно в 3-х плоскостях Фано. Распад между 35 тройками и 15 плоскостями Фано индуцирует PG (3,2) , с 15 точками и 35 линиями. Чтобы создать граф Хоффмана-Синглтона, создайте вершину графа для каждой из 15 плоскостей Фано и 35 триплетов. Соедините каждую плоскость Фано с ее семью тройками, как граф Леви , а также соедините непересекающиеся тройки друг с другом, как нечетный граф O (4).
Очень похожая конструкция из PG (3,2) используется для построения графа Хигмана-Симса , в котором граф Хоффмана-Синглтона является подграфом.
Алгебраические свойства
Группа автоморфизмов графа Хоффман-Singleton является группой порядка 252,000 изоморфна PΣU (3,5 2 ) в полупрямое произведение в проективном специальном унитарной группе БПА (3,5 2 ) с циклической группой порядка 2 , порожденной Автоморфизм Фробениуса . Он действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Хоффмана – Синглтона является симметричным графом . Стабилизатор вершины графа изоморфен симметрической группе S 7 на 7 букв. Множественный стабилизатор ребра изоморфен Aut (A 6 ) = A 6 .2 2 , где A 6 - знакопеременная группа из 6 букв. Оба типа стабилизаторов являются максимальными подгруппами всей группы автоморфизмов графа Хоффмана – Синглтона.
Характеристический полином графа Хоффман-Singleton равно. Следовательно, граф Хоффмана – Синглтона является интегральным графом : его спектр полностью состоит из целых чисел.
Граф Хоффмана-Синглтона имеет ровно 100 независимых наборов размером 15 каждый. Каждый независимый набор не пересекается ровно с 7 другими независимыми наборами. Граф со 100 вершинами, который соединяет непересекающиеся независимые множества, может быть разделен на два подграфа с 50 вершинами, каждый из которых изоморфен графу Хоффмана-Синглтона, в необычном случае самовоспроизводящегося + умножающегося поведения.
Подграфы и надграфы
В графе Хоффмана – Синглтона 1260 5-циклов и 5250 6-циклов. Имеется 525 копий графа Петерсена , каждый из которых 6-цикл принадлежит ровно одному Петерсену. Удаление любого одного Петерсена оставляет копию уникальной (6,5) клетки . [8]
Граф Хоффмана – Синглтона также содержит множество копий графа Мёбиуса – Кантора и графа Хивуда , которые все являются двудольными, и, раскрашивая их чередующимися значениями +1 и -1, можно найти собственный вектор графа с соответствующими собственное значение −3. (Это единственное отрицательное собственное значение графа Хоффмана – Синглтона.) Взятые вместе, эти собственные векторы охватывают −3 собственное подпространство графа Хоффмана – Синглтона, хотя они образуют сильно переполненный базис: существует гораздо больше графов Мёбиуса – Кантора или графов Хивуда. чем есть −3 собственных вектора. Имеется 750 копий графа Хивуда, и граф Хивуда имеет группу автоморфизмов порядка 336. В свою очередь, 750 * 336 = 252000, размер группы автоморфизмов графа Хоффмана-Синглтона, что означает, что граф Хоффмана-Синглтона фиксируется путем фиксации любого графа Хивуда внутри него. Точно так же существует 2625 копий графа Мёбиуса – Кантора, который имеет порядок группы автоморфизмов 96 и 2625 * 96 = 252000, так что аналогичное утверждение верно.
Граф хивуда является особенно заболеваемость графа на плоскости Фано , и так после строительства графа Хоффман-Singleton выше 15 + 35, это сразу показывает много мест , где должны произойти работе Хивуда графики. Возьмем независимый набор размера 15 в графе Хоффмана Синглтона. Их 100 штук. Найдите другой независимый набор, у которого есть 8 общих вершин с первым. Таких соседних независимых множеств 15. Отбросьте 8 общих вершин. 14 оставшихся вершин образуют граф Хивуда. Таким образом, имеется 100 * 15/2 = 750 графиков Хивуда, как было установлено ранее.
Граф Хоффман Синглтон также содержит нечетный граф O (4), граф Кокстера , и графы Тутты-Кокстер как подграфы.
Возьмите любое ребро графа Хоффмана-Синглтона и отбросьте эти две вершины, а также 12 вершин, непосредственно связанных с любой из них. Остающийся граф - это граф Сильвестра с 36 вершинами. Поскольку каждое такое ребро может быть отображено в отдельный граф Сильвестра, в графе Хоффмана Синглтона имеется 175 копий графа Сильвестра.
Граф Хоффмана Синглтона содержится в графе Хигмана-Симса, который, следовательно, является суперграфом.
Смотрите также
- Графы Маккея – Миллера – Ширая , класс графов, включающий граф Хоффмана – Синглтона.
- Таблица наибольших известных графиков заданного диаметра и максимальной степени
Заметки
- ^ a b Вайсштейн, Эрик В. "График Хоффмана-Синглтона" . MathWorld .
- ^ Хафнер, PR "Граф Хоффмана-Синглтона и его автоморфизмы". J. Алгебраический комбинат. 18, 7–12, 2003.
- ^ Ройл, Г. "Re: Что такое краевое хроматическое число Хоффмана-Синглтона?" [email protected] размещение. 28 сентября 2004 г. [1] [ постоянная мертвая ссылка ]
- ^ Кондер, МДЭ; Стокс, К .: "Минимальные родовые вложения графа Хоффмана-Синглтона", препринт, август 2014 г.
- ^ Брауэр, Андрис Э. , граф Хоффмана-Синглтона.
- ^ Хоффман, Алан Дж .; Singleton, Роберт R. (1960), "Мура графы с диаметром 2 и 3" (PDF) , IBM Журнал исследований и разработок , 5 (4): 497-504, DOI : 10,1147 / rd.45.0497 , MR 0140437.
- ^ а б Баэз, Джон (1 февраля 2016 г.), «График Хоффмана – Синглтона» , Visual Insight , Американское математическое общество
- ^ Вонг, Пак-Кен. «О единственности наименьшего графа обхвата 5 и валентности 6». Журнал теории графов . 3 : 407–409. DOI : 10.1002 / jgt.3190030413 .
Рекомендации
- Бенсон, Коннектикут; Лоузи, Н. (1971), "На графике Хоффмана и Singleton", Журнал комбинаторной теории, Series B , 11 (1): 67-79, DOI : 10,1016 / 0095-8956 (71) 90015-3 , ISSN 0095 -8956 , Руководство по ремонту 0281658
- Holton, DA; Шихан, Дж. (1993), График Петерсена , Cambridge University Press , стр.186 и 190, ISBN 0-521-43594-3.