Gewirtz Graph

The Gewirtz graph, sometimes also called the Sims-Gewirtz graph (Brouwer), is an integral graph on 56 vertices and 280 edges that is also a strongly regular graph with parameters . It is illustrated above in eight drawings with 7-fold rotational symmetry and three drawings with 5-fold rotational symmetry due to J. Cross (pers. comm., Jan. 6, 2008).

The Gewirtz graph is implemented in the Wolfram Language as GraphData["GewirtzGraph"].

The Gewirtz graph is the 3-Cossidente-Penttila graph, making it the smallest member of that family.

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 of group 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 have disjoint symbol sets 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 M₂₂ 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.