Hall–Janko graf

Hall–Janko graf
HJ som Foster graf (90 yttre hörn) plus Steiner system S(3,4,10) (10 inre hörn).
Döpt efter	Zvonimir Janko Marshall Hall
Vertices	100
Kanter	1800
Radie	2
Diameter	2
Omkrets	3
Automorfismer	1209600
Kromatiskt nummer	10
Egenskaper	Starkt regelbunden Vertex-transitiv Cayley-graf Eulerian Hamiltonian Integral
Tabell över grafer och parametrar

Inom det matematiska området grafteori är Hall -Janko-grafen , även känd som Hall-Janko-Wales-grafen, en 36- regelbunden oriktad graf med 100 hörn och 1800 kanter.

Det är en rank 3 starkt regelbunden graf med parametrar (100,36,14,12) och en maximal coclique av storlek 10. Denna parameteruppsättning är inte unik, den bestäms dock unikt av dess parametrar som en rank 3 graf. Hall-Janko-grafen konstruerades ursprungligen av D. Wales för att fastställa existensen av Hall-Janko-gruppen som en index 2-undergrupp av dess automorfismgrupp .

Hall–Janko-grafen kan konstrueras av objekt i U ₃ (3), den enkla gruppen av ordning 6048:

• I U ₃ (3) finns det 36 enkla maximala undergrupper av ordningen 168. Dessa är hörnen på en subgraf, U ₃ (3)-grafen. En 168-undergrupp har 14 maximala undergrupper av ordning 24, isomorfa till _S4 . Två 168-undergrupper kallas angränsande när de skär varandra i en 24-undergrupp. U ₃ (3)-grafen är mycket regelbunden, med parametrar (36,14,4,6)
• Det finns 63 involutioner (element av ordning 2). En 168-undergrupp innehåller 21 involutioner, som definieras som grannar.
• Utanför U ₃ (3) låt det finnas en 100:e vertex C , vars grannar är de 36 168-undergrupperna. En 168-undergrupp har då 14 gemensamma grannar med C och totalt 1+14+21 grannar.
• En involution finns i 12 av de 168 undergrupperna. C och en involution är icke-angränsande, med 12 gemensamma grannar.
• Två involutioner definieras som närliggande när de genererar en dihedrisk undergrupp av ordning 8. En involution har 24 involutioner som grannar.

Det karakteristiska polynomet för Hall–Janko-grafen är $(x-36)(x-6)^{36}(x+4)^ {63}$ . Därför är Hall-Janko-grafen en integralgraf : dess spektrum består helt av heltal.