Граф Голла — Янко
Перейти до навігації
Перейти до пошуку
 Граф Голла — Янко як граф Фостера (90 зовнішніх вершин) плюс система Штейнера S(3,4,10) (10 внутрішніх вершин) | |
| Названо на честь | Звонимир Янко Маршал Голл[en] |
|---|---|
| Вершин | 100 |
| Ребер | 1800 |
| Радіус | 2 |
| Діаметр | 2 |
| Обхват | 3 |
| Автоморфізм | 1209600 |
| Хроматичне число | 10 |
| Властивості | сильно регулярний вершинно-транзитивний граф Келі ейлерів гамільтонів цілий |
Граф Голла — Янко, також званий графом Голла — Янко — Велза, це 36-регулярний неорієнтований граф зі 100 вершинами і 1800 ребрами.
Граф має ранг 3 і є сильно регулярним графом з параметрами (100,36,14,12) і найбільшою коклікою[1] розміру 10. Ця множина параметрів не унікальна, проте однозначно визначена параметрами як графу рангу 3. Граф Голла — Янко спочатку побудував Д. Велз для встановлення існування групи Голла — Янко як підгрупи індексу 2 його групи автоморфізмів.
Граф Голла — Янко можна побудувати з об'єктів U3(3), простої групи порядку 6048[2][3]:
- В U3(3) є 36 простих максимальних підгруп порядку 168. Вони будуть вершинами підграфу, U3(3) графу. 168-підгрупа має 14 максимальних підгруп порядку 24, ізоморфних S4. Дві 168-підгрупи вважають суміжними, якщо вони перетинаються по 24-підгрупі. Граф U3(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 інволюції.
Характеристичний многочлен графа Голла — Янко дорівнює . Таким чином, граф Голла — Янко є цілим графом — його спектр складається лише з цілих чисел.
- ↑ Васильев, Вдовин, 2011, с. 425, Множину вершин графу називають коклікою або незалежною, якщо її вершини попарно несуміжні.
- ↑ Brouwer U3(3).
- ↑ Brouwer HJ graph.
- ↑ Wilson, 2009, с. 224.
- Andries E. Brouwer. Hall-Janko graph. Архівовано з джерела 29 липня 2021. Процитовано 29 липня 2021.
- Andries E. Brouwer. U3(3) graph. Архівовано з джерела 1 липня 2017. Процитовано 29 липня 2021.
- Васильев А.В., Вдовин Е.П. Коклики максимального размера в графе простых чисел конечной простой группы // Алгебра и логика. — 2011. — Т. 50, вип. 4 (12 листопада). — С. 425–470.
- Robert A. Wilson. The Finite Simple Groups. — Springer-Verlag, 2009. — Т. 251. — (Graduate Text in Mathematics) — ISBN 978-1-84800-987-5.