It was found by Hoffman & Singleton as example of a Moore graph (a graph of diameter d and girth 2d+1; such graphs are regular, and if the diameter is 2, and the valency is k, the number of vertices is k2 + 1). Two other Moore graphs are known, namely the pentagon and the Petersen graph. If there are other Moore graphs, they must have valency 57 and 3250 vertices.
The Hoffman-Singleton graph is the (7,5)-cage.
It is Hamiltonian.
The second construction uses the fact that it is possible to identify the 35 lines of PG(3,2) with the 35 triples from a 7-set in such a way that intersecting lines correspond to triples that have precisely one element in common. Now take as vertices the 15 points and 35 lines of PG(3,2), let the points form a coclique, let a point be adjacent to a line when they are incident, and let two lines be adjacent when the corresponding triples are disjoint.
The third construction produces the Higman-Sims graph, together with a split into two copies of Γ. In the Steiner system S(4,7,23), fix an symbol a. Construct the Higman-Sims graph on 1+22+77 points by taking a point x, the 22 symbols distinct from a and the 77 blocks containing a, where blocks are adjacent when they meet precisely in {a}. Now let B be a block of S(4,7,23) not containing a. We find a partition (1+7+42)+(15+35) of the 1+22+77 induced by B (the 42 blocks are those meeting B in one point, the 35 those meeting B in three points), and both 1+7+42 and 15+35 induce a Hoffman-Singleton graph.
a) A vertex. There are 50 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is S7 with vertex orbit sizes 1+7+42. The subgraph induced on the second subconstituent is the unique distance-regular graph with intersection array {6,5,1;1,1,6}.
b) A 15-coclique. There are 100 of these, forming a single orbit. The stabilizer is A7 with vertex orbit sizes 15+35. The complement of a 15-coclique is the unique distance-regular graph with intersection array {4,3,3;1,1,2}, namely the Odd graph O4 of disjoint triples in a 7-set. It has full group S7, with point stabilizer S3×S4. The group is twice that of the Hoffman-Singleton graph since this graph can be extended to a Hoffman-Singleton graph in two ways; both occur in the Higman-Sims graph.
Two 15-cocliques meet in 0 (7x), 3 (35x), 5 (42x), 8 (15x) or 15 (1x) points. Meeting in 0, 5 or 15 is an equivalence relation, and the collection of 100 15-cocliques is the union of two collections of size 50. Being disjoint induces the structure of a Hoffman-Singleton graph on both.
The graph on the 15-cocliques, adjacent when they meet in 8 points, is the unique distance-regular graph with intersection array {15,14,10,3;1,5,12,15}. It has full group PSU(3,5).2 with point stabilizer A7 and edge stabilizer L2(7):2 (see below).
The graph on the 15-cocliques, adjacent when they meet in 0 or 8 is the Higman-Sims graph.
The two sets of 50 15-cocliques and the 50 vertices play a similar role (and there is an outer automorphism that interchanges the three). Thus, we can make a graph on 150 vertices, regular of valency 37, with a partition 50+50+50 such that the union of any two parts is the Higman-Sims graph.
c) Split into two copies of 5C5. There are 126 of these, forming a single orbit. (The construction given above gives an explicit split.) The stabilizer is 5+1+2:8:2 with vertex orbit size 50.
d) An edge. There are 175 of these, forming a single orbit. The stabilizer of one is A6.22 with vertex orbit sizes 2+12+36.
The line graph of the Hoffman-Singleton graph is the unique distance-regular graph with intersection array {12,6,5;1,1,4}. Its distance-2 graph is strongly regular with parameters v = 175, k = 72, λ = 20, μ = 36. (It is the collinearity graph of a partial geometry pg(5,18,2) constructed by Haemers. The collinearity graph of the dual pg(18,5,2) has parameters v = 630, k = 85, λ = 20, μ = 10, and full automorphism group Alt(7), transitive on the points.)
The subgraph induced on the orbit of size 36 is the Sylvester graph, the unique distance-regular graph with intersection array {5,4,2;1,1,4}.
e) A pair of disjoint 15-cocliques. There are 350 of these, forming a single orbit. The stabilizer of one is M10 with vertex orbit sizes 20+30.
The subgraph induced on the orbit of size 20 is 10K2.
The subgraph induced on the orbit of size 30 is Tutte's 8-cage, the incidence graph of the generalized quadrangle GQ(2,2).
f) A Petersen graph. There are 525 of these, forming a single orbit. The stabilizer of one is 2S5.2 with vertex orbit sizes 10+40.
The subgraph induced on the orbit of size 40 is the unique (6,5)-cage.
Each hexagon of Γ is contained in a unique Petersen graph.
Each Petersen graph is split 5+5 in 6 splits into two 5C5. Each split into two 5C5 determines 25 Petersen graphs. Each pair of splits determines a unique Petersen graph. In this way we find the unital in PG(2,52), with splits into two 5C5 as points, and Petersen graphs as lines.
g) A Heawood graph. There are 750 of these, forming a single orbit. The stabilizer of one is L2(7):2 with vertex orbit sizes 8+14+28. The 14 induces the Heawood graph.
Heawood subgraphs are equivalent to pairs of 15-cocliques meeting in 8 points: each half occurs in a unique 15-coclique and these two 15-cocliques meet in 8 points (and conversely, two 15-cocliques meeting in 8 points carry a Heawood graph on their symmetric difference).
The 28 induces the Coxeter graph.
A.E. Brouwer & J.H. van Lint, Strongly regular graphs and partial geometries, in: Enumeration and Design - Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982, D.M. Jackson & S.A. Vanstone (eds.) Academic Press, Toronto (1984) 85-122.
W.H. Haemers, A new partial geometry constructed from the Hoffman-Singleton graph, Finite Geometries and designs, Proc. Second Isle of Thorns Conference 1980, P.J. Cameron, J.W.P. Hirschfeld & D.R. Hughes (eds.), London Math. Soc. Lecture Note Ser. 49, Cambridge University Press, Cambridge (1981) 119-127.
A.J. Hoffman & R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Develop. 4 (1960) 497-504.
L.O. James, A combinatorial proof that the Moore (7,2) graph is unique, Utilitas Math. 5 (1974) 79-84.
G. Royle, Re: What is the Edge Chromatic Number of Hoffman-Singleton?, GRAPHNET@listserv.nodak.edu posting, 2004-09-29.
[BCN], Section 13.1.