Higman-Sims Graph

The Higman-Sims graph is the unique strongly regular graph on 100 nodes (Higman and Sims 1968, Brouwer 1983, Brouwer and Haemers 1993). It was also constructed independently in Theorem 5.3 of Goethals and Seidel (1970). It has regular parameters , where is the number of vertices, is the number of neighbors of each vertex, is the number of common neighbors shared by every adjacent pair of vertices, and is the number of common neighbors shared by every nonadjacent pair or vertices.

The Higman-Sims graph is distance-regular with intersection array . It is also distance-transitive.

It is an integral graph with graph spectrum .

The embedding given at the top of this article is the graph sum of the ten graphs illustrated above which arise in the construction due to Hafner (2004).

It can be constructed by beginning with the 77 vectors of length 7 in the Witt design that contain the symbol 1, dropping the 1, and renumbering the remaining elements from 1 to 22. Consider these vectors as vertices, and adjoin an additional 22 vertices and one special vertex . Now construct the 616 edges between whenever the intersection of and is empty, the 462 edges between and whenever is a member of , and the 22 edges between and every . Then the result graph on 100 vertices and 1100 edges is the Higman-Sims graph.

The Higman-Sims graph can be constructed from the Hoffman-Singleton graph by treating the latter's 100 independent vertex sets of size 15 as vertices and connecting by edges those pairs of independent sets which share exactly 0 or 8 elements.

It can also be constructed from the Leech lattice by starting with three lattice points that form the vertices of an isosceles triangle with side lengths of 2, , and , identifying the exactly 100 lattice points that are at distance 2 from each triangle vertex, and joining two points with an edge if they are separated by distance . The resulting graph is the Higman-Sims graph (Conway and Sloane 1999, pp. 292-293; Gaucher 2013; Brouwer and van Maldeghem 2022, p. 303).

The automorphism group of the Higman-Sims graph acts transitively on its edges (Brouwer and Haemers 1993).

The graph obtained by vertex deletion of the neighbors of a point in the Higman-Sims graph (which is not, as claimed by van Dam and Haemers 2003, the subgraph induced by the vertex neighbors) is the M22 graph.