| Hall–Janko graph | |
|---|---|
 HJ as Foster graph (90 outer vertices) plus Steiner system S(3,4,10) (10 inner vertices). | |
| Named after | Zvonimir Janko Marshall Hall |
| Vertices | 100 |
| Edges | 1800 |
| Radius | 2 |
| Diameter | 2 |
| Girth | 3 |
| Automorphisms | 1209600 |
| Chromatic number | 10 |
| Properties | Strongly regular Vertex-transitive Cayley graph Eulerian Hamiltonian Integral |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the Hall–Janko graph, also known as the Hall-Janko-Wales graph, is a 36-regular undirected graph with 100 vertices and 1800 edges. [1]
Mathematics includes the study of such topics as quantity, structure, space, and change.
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges, then called arrows, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph of odd degree will contain an even number of vertices.
It is a 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 2 subgroup of its automorphism group.
In mathematical finite group theory, a rank 3 permutation group acts transitively on a set such that the stabilizer of a point has 3 orbits. The study of these groups was started by Higman. Several of the sporadic simple groups were discovered as rank 3 permutation groups.
In graph theory, a strongly regular graph is defined as follows. Let G = be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:
In mathematics, specifically group theory, the index of a subgroup H in a group G is the "relative size" of H in G: equivalently, the number of "copies" (cosets) of H that fill up G. For example, if H has index 2 in G, then intuitively half of the elements of G lie in H. The index of H in G is usually denoted |G : H| or [G : H] or (G:H).
The Hall–Janko graph can be constructed out of objects in U3(3), the simple group of order 6048: [2] [3]
- 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 generate a dihedral subgroup of order 8. [4] An involution has 24 involutions as neighbors.
The characteristic polynomial of the Hall–Janko graph is . Therefore the Hall–Janko graph is an integral graph: its spectrum consists entirely of integers.
In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjacency matrix are integers.
In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.
