Gewirtz Graph

The Gewirtz graph, sometimes also called the Sims-Gewirtz graph (Brouwer), is an integral graph on 56 nodes and 280 edges that is also a regular graph of order 10. It is illustrated above in eight embeddings with 7-fold symmetry and three embeddings with 5-fold symmetry due to Jonathan Cross (pers. comm., Jan. 6, 2008).

The Gewirtz graph has graph diameter 2, girth 4, graph radius 2, and is Hamiltonian and nonplanar. It is the unique graph on 56 vertices having graph spectrum (Gewirtz 1969, Brouwer and Haemers 1993). It is therefore an integral graph. It has chromatic number 4, edge connectivity 10 and vertex connectivity 10. Its automorphism group is or order .

It is distance-regular with intersection array and is also distance-transitive.

It can be constructed from the 77 vectors of length 7 and containing a given symbol, say 1, in the Witt design as follows. In this set of 77 vectors, remove the symbol 1 and renumber. Then pick the 56 vectors from these that do not contain the symbol 1, and again renumber. The graph with vertices on these vectors and edges between vertices whenever their corresponding vectors as disjoint then gives the Gewirtz graph.

The graph can be constructed explicitly by taking the following 56 words (which are precisely the words in the construction of the M22 graph that lack the letter "v"; excluding any other letter works as well) as vertices and constructing edges for each pair of vertices that have no letters in common.