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

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

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

Граф має і є сильно регулярним графом з параметрами (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}$ . Таким чином, граф Голла — Янко є цілим графом — його спектр складається лише з цілих чисел.

Див. також

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

Примітки

Васильев, Вдовин, 2011, с. 425, Множину вершин графу називають коклікою або незалежною, якщо її вершини попарно несуміжні.
Brouwer U3(3).
Brouwer HJ graph.
Wilson, 2009, с. 224.

Література

Andries E. Brouwer. Hall-Janko graph. з джерела 29 липня 2021. Процитовано 29 липня 2021.
Andries E. Brouwer. U₃(3) graph. з джерела 1 липня 2017. Процитовано 29 липня 2021.
Васильев А.В., Вдовин Е.П. Коклики максимального размера в графе простых чисел конечной простой группы // Алгебра и логика. — 2011. — Т. 50, вип. 4 (10 липня). — С. 425–470.
Robert A. Wilson. The Finite Simple Groups. — Springer-Verlag, 2009. — Т. 251. — (Graduate Text in Mathematics) — .

[FOOTNOTEВасильев,_Вдовин2011425Множину_вершин_графу_називають_''коклікою''_або_''незалежною'',_якщо_її_вершини_попарно_несуміжні-1] Васильев, Вдовин, 2011, с. 425, Множину вершин графу називають коклікою або незалежною, якщо її вершини попарно несуміжні.

[FOOTNOTEBrouwer_U3(3)-2] Brouwer U3(3).

[FOOTNOTEBrouwer_HJ_graph-3] Brouwer HJ graph.

[FOOTNOTEWilson2009224-4] Wilson, 2009, с. 224.