У математичній теорії графів, граф Гофмана — Синглтона це 7-регулярнимй неорієнтованимй граф зі 50 вершинами і 175 ребрами. Це єдиний сильно регулярний граф із параметрами (50,7,0,1). Його побудували [en] і Роберт Синглтон, коли намагалися класифікувати всі графи Мура, він є графом Мура з найвищим порядком, для якого відомо, що граф існує. Оскільки це граф Мура, в якому кожна вершина має степінь 7, а обхват 5, тоді він є (7,5)-кліткою.
Граф Гофмана — Синглтона | |
---|---|
![]() | |
Названо на честь | [en] |
Вершин | 50 |
Ребер | 175 |
Радіус | 2 |
Діаметр | 2 |
Обхват | 5 |
Автоморфізм | 252 000 ((3,52):2) |
Хроматичне число | 4 |
Хроматичний індекс | 7 |
Властивості | Сильно регулярний Симетричний Гамільтонів Цілий Клітка Граф Мура |
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODFMelU0TDBodlptWnRZVzVmYzJsdVoyeGxkRzl1WDJkeVlYQm9YMk5wY21Oc1pUSXVaMmxtTHpJMU1IQjRMVWh2Wm1adFlXNWZjMmx1WjJ4bGRHOXVYMmR5WVhCb1gyTnBjbU5zWlRJdVoybG0uZ2lm.gif)
Побудова
Тут наведено дві побудови графа Гофмана — Синглтона.
Побудова з п'ятикутників та пентаграм
Візьміть п'ять п'ятикутників Ph і п'ять пентаграми Qi, так щоб вершина j з Ph була суміжною з вершинами j−1 та j+1 з Ph і вершина j з Qi була суміжною з вершинами j−2 та j+2 з Qi. Тепер приєднайте вершину j з Ph до вершини h·i+j з Qi. (Всі індекси за модулем 5.)
Побудова з площин Фано
Будь-яку множину зі семи точок (як абстрактних математичних об'єктів) можна перетворити на площину Фано, додавши сім ліній на них. Кількість різних способів зробити це — 30 = 7!/168. Тут 7! — це число перестановок із семи точок. 168 — число симетрій площини Фано, і, як наслідок, кількість перестановок, які зберігають будь-який заданий набір ліній, які утворюють площину Фано. Серед цих 30 різних площин Фано, кожна підмножина трьох точок використовується як лінія в 6 з 30 площин. Для будь-якої з цих 30 площин Фано, є 14 інших, які розділяють принаймні один рядок з ними.
Також сама множина з семи точок теж має 35 різних підмножин, які складаються з трьох елементів («тріад»), підрахованих за допомогою біноміального коефіцієнта .
Граф Гофмана — Синглтона в такому разі можна побудувати з двох множин вершин:
- по одній для кожної площини Фано в наборі з 15 площин, які формуються вибором однієї довільної і 14 інших, які розділяють лінію з ним, та
- по одній для кожної тріади.
Ці вершини з'єднані ребрами двох типів:
- між кожною вибраною площиною Фано і 7 тріад, які відповідають її лінії, та
- між тріадами зі спільних точок.
Алгебраїчні властивості
Група автоморфізмів графа Гофмана — Синглтона є групою порядку 252 000 ізоморфною PΣU(3,52) напівпрямому добутку [en] PSU(3,52) з циклічною групою порядку 2, породженої автоморфізму Фробеніуса. Він діє транзитивно на вершини, ребра і дуги графа. Тому граф Гофмана — Синглтона симетричний граф. Стабілізатор вершини графа є ізоморфом симетричної групи S7 по 7 букв. Стабілізатор множини ребер ізоморфний Aut(A6)=A6.22, де A6 є знакозмінною групою по 6 букв. Обидва з цих двох типів стабілізаторів є максимальними підгрупами всієї групи автоморфізмів графа Гофмана — Синглтона.
Характеристичний поліном графа Гофмана — Синглтона дорівнює . Тому граф Гофмана — Синглтона є інтегральним графом: його спектр повністю складається з цілих чисел.
Підграфи
Використовуючи тільки той факт, що граф Гофмана — Синглтона є сильно регулярним графом із параметрами (50,7,0,1), можна показати, що існує 1260 5-циклів, що містяться у графі Гофмана — Синглтона.
Крім того, граф Гофмана — Синглтона містить 525 копій графа Петерсена. Видалення будь-якого одного з них залишає копію унікальної (6,5)-клітки.
Див. також
- Задача степеня — діаметра
- [en]
- (Граф Гофмана)
Примітки
- Weisstein, Eric W. Hoffman-Singleton Graph(англ.) на сайті Wolfram MathWorld.
- Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
- Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. Sept. 28, 2004. [1][недоступне посилання]
- , , архів оригіналу за 3 березня 2016, процитовано 5 грудня 2016.
- Hoffman, Alan J.; Singleton, Robert R. (1960), (PDF), IBM Journal of Research and Development, 5 (4): 497—504, doi:10.1147/rd.45.0497, MR 0140437, архів оригіналу (PDF) за 18 травня 2008, процитовано 5 грудня 2016.
- (1 лютого 2016), , Visual Insight, American Mathematical Society, архів оригіналу за 14 листопада 2016, процитовано 5 грудня 2016
- Wong, Pak-Ken. On the uniqueness of the smallest graph of girth 5 and valency 6. . 3: 407—409. doi:10.1002/jgt.3190030413.
Посилання
- Benson, C. T.; Losey, N. E. (1971), On a graph of Hoffman and Singleton, Journal of Combinatorial Theory. Series B, 11 (1): 67—79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR 0281658
- Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, с. 186 and 190, ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет