Hall – Jankov graf - Hall–Janko graph

Hall – Jankov graf
HJ as Pěstounský graf (90 vnějších vrcholů) plus Steinerův systém S (3,4,10) (10 vnitřních vrcholů).
Pojmenoval podle	Zvonimir Janko Marshall Hall
Vrcholy	100
Hrany	1800
Poloměr	2
Průměr	2
Obvod	3
Automorfismy	1209600
Chromatické číslo	10
Vlastnosti	Silně pravidelné Vrchol-tranzitivní Cayleyův graf Eulerian Hamiltonian Integrální
Tabulka grafů a parametrů

V matematický pole teorie grafů, Hall – Jankov graf, také známý jako Hall-Janko-Wales graf, je 36-pravidelný neorientovaný graf se 100 vrcholy a 1800 hranami.^[1]

Je to pozice 3 silně pravidelný graf s parametry (100,36,14,12) a maximem coclique o velikosti 10. Tato sada parametrů není jedinečná, je však jednoznačně určena svými parametry jako graf 3. úrovně. Hall-Jankov graf byl původně sestrojen D. Walesem za účelem zjištění existence Skupina Hall-Janko jako index 2 jeho podskupina automorfická skupina.

Hall-Jankov graf lze sestrojit z objektů v U.₃(3), jednoduchá skupina objednávky 6048:^[2][3]

• V U₃(3) existuje 36 jednoduchých maximálních podskupin řádu 168. Jedná se o vrcholy podgrafu, U₃(3) graf. Podskupina 168 má 14 maximálních podskupin řádu 24, izomorfních k S.₄. Dvě 168 podskupin se nazývají sousedící, když se protínají v 24 podskupině. U₃(3) graf je silně pravidelný, s parametry (36,14,4,6)
• Existuje 63 involucí (prvky řádu 2). Podskupina 168 obsahuje 21 involucí, které jsou definovány jako sousedé.
• Mimo U₃(3) ať existuje 100. vrchol C, jehož sousedy jsou 36 168 podskupin. Podskupina 168 má pak 14 společných sousedů s C a ve všech sousedech 1 + 14 + 21.
• Involuce se nachází ve 12 ze 168 podskupin. C a involuce nesousedí s 12 společnými sousedy.
• Dvě involuce jsou definovány jako sousedící, když generují vzepětí podskupinu řádu 8.^[4] Involuce má jako sousedé 24 involucí.

Charakteristický polynom grafu Hall – Janko je ${ displaystyle (x-36) (x-6) ^ {36} (x + 4) ^ {63}}$. Graf Hall – Janko je tedy integrální graf: své spektrum skládá se výhradně z celých čísel.

Reference