Editing Hall–Janko graph

{{infobox graph
 | name = Hall–Janko graph
 | image = [[Image:Hall janko graph.svg|300px]]
 | image_caption = HJ as [[Foster graph]] (90 outer vertices) plus [[Steiner system]] S(3,4,10) (10 inner vertices).
 | namesake = [[Zvonimir Janko]]<br>[[Marshall Hall (mathematician)|Marshall Hall]]
 | vertices = 100
 | edges = 1800
 | automorphisms = 1209600
 | diameter = 2
 | girth = 3
 | radius = 2
 | chromatic_number = 10
 | chromatic_index =
 | properties = [[Strongly regular graph|Strongly regular]]<br>[[Vertex-transitive graph|Vertex-transitive]]<br>[[Cayley graph]]<br>[[Eulerian graph|Eulerian]]<br>[[Hamiltonian graph|Hamiltonian]]<br>[[integral graph|Integral]]
}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Hall–Janko graph''', also known as the '''Hall-Janko-Wales graph''', is a 36-[[regular graph|regular]] [[undirected graph]] with 100 vertices and 1800 edges.<ref>{{MathWorld | urlname=Hall-JankoGraph | title=Hall-Janko graph}}</ref>

It is a [[Rank 3 permutation group|rank 3]] [[strongly regular graph]] with parameters (100,36,14,12) and a maximum [[coclique]] of size 10. This parameter set is not unique, it is however uniquely determined by its parameters as a rank 3 graph. The Hall–Janko graph was originally constructed by D. Wales to establish the existence of the [[Hall-Janko group]] as an [[Index of a subgroup|index]] 2 subgroup of its [[Graph automorphism|automorphism group]]. 

The Hall–Janko graph can be constructed out of objects in U<sub>3</sub>(3), the simple group of order 6048:<ref>Andries E. Brouwer, "[http://www.win.tue.nl/~aeb/drg/graphs/HallJanko.html Hall-Janko graph]".</ref><ref>Andries E. Brouwer, "[http://www.win.tue.nl/~aeb/drg/graphs/U3_3.html U<sub>3</sub>(3) graph]".</ref>
* In U<sub>3</sub>(3) there are 36 simple maximal subgroups of order 168. These are the vertices of a subgraph, the U<sub>3</sub>(3) graph. A 168-subgroup has 14 maximal subgroups of order 24, isomorphic to S<sub>4</sub>. Two 168-subgroups are called adjacent when they intersect in a 24-subgroup. The U<sub>3</sub>(3) graph is strongly regular, with parameters (36,14,4,6)
* There are 63 involutions (elements of order 2). A 168-subgroup contains 21 involutions, which are defined to be neighbors.
* Outside U<sub>3</sub>(3) let there be a 100th vertex '''C''', whose neighbors are the 36 168-subgroups. A  168-subgroup then has 14 common neighbors with C and in all 1+14+21 neighbors.
* An involution is found in 12 of the 168-subgroups. C and an involution are non-adjacent, with 12 common neighbors.
* Two involutions are defined as adjacent when they generate a dihedral subgroup of order 8.<ref>Robert A. Wilson, 'The Finite Simple Groups', Springer-Verlag (2009), p. 224.</ref> An involution has 24 involutions as neighbors.

The characteristic polynomial of the Hall–Janko graph is <math>(x-36)(x-6)^{36}(x+4)^{63}</math>. Therefore the Hall–Janko graph is an [[integral graph]]: its [[Spectral graph theory|spectrum]] consists entirely of integers.

==References==
{{reflist}}

{{DEFAULTSORT:Hall-Janko Graph}}
[[Category:Group theory]]
[[Category:Individual graphs]]
[[Category:Regular graphs]]