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

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

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

Граф має ранг 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.
  • Andries E. Brouwer. U3(3) graph.
  • Васильев А.В., Вдовин Е.П. Коклики максимального размера в графе простых чисел конечной простой группы // Алгебра и логика. — 2011. — Т. 50, вип. 4 (3 листопада). — С. 425–470.
  • Robert A. Wilson. The Finite Simple Groups. — Springer-Verlag, 2009. — Т. 251. — (Graduate Text in Mathematics) — ISBN 978-1-84800-987-5.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.