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

Граф Голла — Янко як граф Фостера (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 інволюції.

Характеристичний многочлен графа Голла — Янко дорівнює . Таким чином, граф Голла — Янко є цілим графом — його спектр складається лише з цілих чисел.

Див. також

Примітки

  1. ↑ Васильев, Вдовин, 2011, с. 425, Множину вершин графу називають коклікою або незалежною, якщо її вершини попарно несуміжні.
  2. ↑ Brouwer U3(3).
  3. ↑ Brouwer HJ graph.
  4. ↑ 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 (19 січня). — С. 425–470.
  • Robert A. Wilson. The Finite Simple Groups. — Springer-Verlag, 2009. — Т. 251. — (Graduate Text in Mathematics) — ISBN 978-1-84800-987-5.