Truncated Witt Graph

The truncated Witt graph is the graph on 506 vertices related to a 4-(23,8,4) design (Brouwer et al. 1989, p. 367). It is called the M_(23) graph by van Dam and Haemers (2003), who note that it is also determined by spectrum. Its spectrum is given by (-8)^(22)(-3)^(253)4^(230)15^1, 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 {15,14,12;1,1,9}. It is also distance-transitive.

See also

Determined by Spectrum, Doubly Truncated Witt Graph, Iofinova-Ivanov Graphs, Large Witt Graph, Witt Design

Explore with Wolfram|Alpha


Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "The Truncated Witt Graph Associated to M_(23)." §11.4B in Distance Regular Graphs. New York: Springer-Verlag, pp. 367-368, "Truncated Witt Graph." Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

Cite this as:

Weisstein, Eric W. "Truncated Witt Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications