Higman–Sims graph

Higman–Sims graph
Drawing based on Paul R. Hafner's construction.
Named after	Donald G. Higman Charles C. Sims
Vertices	100
Edges	1100
Radius	2
Diameter	2
Girth	4
Automorphisms	88,704,000 (HS:2)
Properties	Strongly regular Edge-transitive Hamiltonian Eulerian

In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph with 100 vertices and valency 22, where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was first constructed by Mesner (1956) and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, and that group is a subgroup of index two in the group of automorphisms of the Higman–Sims graph.

Construction begins with the M₂₂ graph, whose 77 vertices are the blocks of the S(3,6,22) Steiner system W₂₂. Adjacent vertices are defined to be disjoint blocks. This graph is strongly regular; any vertex has 16 neighbors, any 2 adjacent vertices have no common neighbors, and any 2 non-adjacent vertices have 4 common neighbors. This graph has M₂₂:2 as its automorphism group, M₂₂ being a Mathieu group.

The Higman–Sims graph is then formed by appending the 22 points of W₂₂ and a 100th vertex C. The neighbors of C are defined to be those 22 points. A point adjacent to a block is defined to be one that is included.

A Higman–Sims graph can be partitioned into two copies of the Hoffman–Singleton graph in 352 ways.

The automorphism group of the Higman–Sims graph is a group of order 88,704,000 isomorphic to the semidirect product of the Higman–Sims group of order 44,352,000 with the cyclic group of order 2. It has automorphisms that take any edge to any other edge, making the Higman–Sims graph an edge-transitive graph.