- Hall–Janko graph
[
HJ asFoster graph (90 outer vertices) plusSteiner system S(3,4,10) (10 inner vertices).]In
graph theory , the Hall–Janko graph, also known as the Hall-Janko-Wales graph, is arank 3 strongly regular graph with parameters (100,36,14,12) and a maximumcoclique 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 theHall-Janko group as an index 2 subgroup of its automorphism group.The Hall-Janko graph can be constructed out of objects in U3(3), the simple group of order 6048:
* In U3(3) there are 36 simple maximal subgroups of order 168. These are the vertices of a subgraph, the U3(3) graph. A 168-subgroup has 14 maximal subgroups of order 24, isomorphic to S4. Two 168-subgroups are called adjacent when they intersect in a 24-subgroup. The U3(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 U3(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 are shared by 4 168-subgroups. An involution has 24 involutions as neighbors.References
* [http://www.win.tue.nl/~aeb/drg/graphs/HallJanko.html Hall-Janko graph]
* [http://www.win.tue.nl/~aeb/drg/graphs/U3_3.html U3(3) graph]
Wikimedia Foundation. 2010.