Граф Голла — Янко

Граф Голла — Янко, також званий графом Голла — Янко — Велза, це 36-регулярний неорієнтований граф зі 100 вершинами і 1800 ребрами.

Граф Голла — Янко як граф Фостера (90 зовнішніх вершин) плюс система Штейнера S(3,4,10) (10 внутрішніх вершин)
Названо на честь	Звонимир Янко Маршал Голл
Вершин	100
Ребер	1800
Радіус	2
Діаметр	2
Обхват	3
Автоморфізм	1209600
Хроматичне число	10
Властивості	сильно регулярний вершинно-транзитивний граф Келі ейлерів гамільтонів цілий

Граф має ранг 3 і є сильно регулярним графом з параметрами (100,36,14,12) і найбільшою коклікою розміру 10. Ця множина параметрів не унікальна, проте однозначно визначена параметрами як графу рангу 3. Граф Голла — Янко спочатку побудував Д. Велз для встановлення існування групи Голла — Янко як підгрупи індексу 2 його групи автоморфізмів.

Граф Голла — Янко можна побудувати з об'єктів U₃(3), простої групи порядку 6048:

• В U₃(3) є 36 простих максимальних підгруп порядку 168. Вони будуть вершинами підграфу, U₃(3) графу. 168-підгрупа має 14 максимальних підгруп порядку 24, ізоморфних S₄. Дві 168-підгрупи вважають суміжними, якщо вони перетинаються по 24-підгрупі. Граф U₃(3) є строго регулярним графом з параметрами (36,14,4,6)
• Є 63 інволюції (елементів порядку 2). 168-підгрупа містить 21 інволюцію, які вважаються сусідами.
• Поза U₃(3) нехай є 100-а вершина C, сусідами якої є 36 168-підгруп. 168-підгрупа тоді має 14 спільних сусідів з C і 1+14+21 сусідів усього.
• Інволюція міститься в 12 168-підгрупах. Вершина C і інволюція не суміжні, але мають 12 спільних сусідів.
• Дві інволюції вважаються суміжними, якщо вони генерують діедральну підгрупу порядку 8. Інволюція має сусідами 24 інволюції.

Характеристичний многочлен графа Голла — Янко дорівнює $(x-36)(x-6)^{36}(x+4)^{63}$. Таким чином, граф Голла — Янко є цілим графом — його спектр складається лише з цілих чисел.

Див. також

• Майже многокутник

Література

• Andries E. Brouwer. Hall-Janko graph. Архівовано з джерела 29 липня 2021. Процитовано 29 липня 2021.
• Andries E. Brouwer. U₃(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.