Truncated Witt Graph

The truncated Witt graph is the graph on 506 vertices related to a 4- 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 spectrum is given by , making it an integral graph.

It can be constructed by taking the 506 vectors of length 15 in the Witt design and considering them as vertices. Edges are then drawn between any pair of vertices whose intersection does not contain exactly 7 symbols. The resulting graph on 506 vertices and 3795 edges is the truncated Witt graph.

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 subgraph induced by the 506 vertices on the large Witt graph.

The truncated Witt graph is distance-regular with intersection array . It is also distance-transitive.