Hoffman–Singleton graph

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

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).^[5] 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.^[6] 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.^[7]

See also

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

Notes

1. Weisstein, Eric W., "Hoffman-Singleton Graph", MathWorld.
2. Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
3. Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" [e-mail] posting. Sept. 28, 2004.
4. Conder, M.D.E.; Stokes, K.: "Minimum genus embeddings of the Hoffman-Singleton graph", preprint, August 2014.
5. Brouwer, Andries E., Hoffman-Singleton graph.
6. Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437.
7. Wong, Pak-Ken. "On the uniqueness of the smallest graph of girth 5 and valency 6". Journal of Graph Theory 3: 407—409.

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.