Truncated Witt Graph

The truncated Witt graph is the graph on 506 vertices related to a 4- block design (Brouwer et al. 1989, p. 367). It is called the graph by van Dam and Haemers (2003), who note that it is also determined by spectrum. Its graph spectrum is given by , making it an integral graph.

It can be represented by the 506 subsets of size 15 obtained by complementing the octads that avoid a fixed coordinate position in the extended binary Golay code. The complements are taken within the remaining 23 coordinate positions. Two such subsets are adjacent iff their intersection contains exactly 7 elements. The resulting graph has 506 vertices and 3795 edges.

Alternately, it may be constructed from the large Witt graph on 759 vertices which has as vertices the 759 codewords of weight 8 in the extended binary Golay code. Picking any one coordinate position, 253 codewords have a 1, while 506 have a 0. The truncated Witt graph is then the induced subgraph on the 506 vertices on the large Witt graph.

The truncated Witt graph is distance-regular with intersection array . It is also distance-transitive. Its automorphism group is the Mathieu group M₂₃, of group order (DistanceRegular.org).