Hoffman–Singleton graph

Hoffman–Singleton graph
Named after	Alan J. Hoffman Robert R. Singleton
Vertices	50
Edges	175
Radius	2
Diameter	2
Girth	5
Automorphisms	252,000 (PSU(3,52):2)
Chromatic number	4
Chromatic index	7
Genus	29
Properties	Strongly regular Symmetric Hamiltonian Integral Cage Moore graph
Table of graphs and parameters

The Hoffman–Singleton graph. The subgraph of blue edges is a sum of ten disjoint pentagons.

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

Construction

There are many ways to construct the Hoffman-Singleton graph.

Construction from pentagons and pentagrams

Take five pentagons P_h and five pentagrams Q_i, so that vertex j of P_h is adjacent to vertices j-1 and j+1 of P_h and vertex j of Q_i is adjacent to vertices j-2 and j+2 of Q_i. Now join vertex j of P_h to vertex h·i+j of Q_i. (All indices are modulo 5.)

Construction from triads and Fano planes

Take the Fano plane and permute its 7 points to make a set of 30 Fanos. Pick any one of these 30 Fanos; there will be another 14 Fanos that share exactly one triplet ("line") with the first one. Take those 15 Fanos and discard the other 15. Take the ⁷C₃ = 35 triads on 7 numbers. Now connect a triad to a Fano that includes it, and connect disjoint triads to each other. The resulting graph is the Hoffman-Singleton graph, with the 50 vertices corresponding to the 35 triads + 15 Fanos, and each vertex has degree 7. Vertices corresponding to Fanos are linked to 7 triads by definition, as the Fano plane has 7 lines. Each triad is linked to 3 different Fanos that include it, and to 4 other triads with which it is disjoint.

Algebraic properties

The automorphism group of the Hoffman–Singleton graph is a group of order 252,000 isomorphic to PΣU(3,5²) the semidirect product of the projective special unitary group PSU(3,5²) with the cyclic group of order 2 generated by the Frobenius automorphism. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Hoffman–Singleton graph is a symmetric graph. The stabilizer of a vertex of the graph is isomorphic to the symmetric group S₇ on 7 letters. The setwise stabilizer of an edge is isomorphic to Aut(A₆)=A₆.2², where A₆ is the alternating group on 6 letters. Both of the two types of stabilizers are maximal subgroups of the whole automorphism group of the Hoffman-Singleton graph.

The characteristic polynomial of the Hoffman–Singleton graph is equal to $(x-7)(x-2)^{28}(x+3)^{21}$. Therefore the Hoffman–Singleton graph is an integral graph: its spectrum consists entirely of integers.

Subgraphs

Using only the fact that the Hoffman–Singleton graph is a strongly regular graph with parameters (50,7,0,1), it can be shown that there are 1260 5-cycles contained in the Hoffman–Singleton graph.

Additionally, the Hoffman–Singleton graph contains 525 copies of the Petersen graph. Removing any one of these leaves a copy of the unique (6,5) cage.

See also

• Table of the largest known graphs of a given diameter and maximal degree

References

• Benson, C. T.; Losey, N. E. (1971), "On a graph of Hoffman and Singleton", Journal of Combinatorial Theory. Series B, 11 (1): 67–79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR 0281658
• Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, pp. 186 and 190, ISBN 0-521-43594-3.