TOPICS

# 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.

 abcilu abdfrs abejop abgmnq acdghp acfjnt ackmos ademtu adjklq aefgik aehlns afhoqu aglort ahijmr aipqst aknpru bcdekn bchjqs bcmprt bdgijt bdhlmo beflqt beghru bfhinp bfjkmu bgklps bikoqr bnostu cdfimq cdjoru cefpsu cegjlm cehiot cfhklr cginrs cgkqtu clnopq degoqs deilpr dfglnu dfkopt dhiksu dhnqrt djmnps efmnor ehkmpq eijnqu ejkrst fghmst fgjpqr fijlos ghjkno gimopu hjlptu iklmnt lmqrsu

Goethals-Seidel Graphs, Graph Spectrum, Integral Graph, M22 Graph, Witt Design

## Explore with Wolfram|Alpha

More things to try:

## References

Brouwer, A. E. "Sims-Gewirtz Graph." http://www.win.tue.nl/~aeb/drg/graphs/Sims-Gewirtz.html.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.DistanceRegular.org. "Gewirtz Graph." http://www.distanceregular.org/graphs/gewirtz.html.Gewirtz, A. "The Uniqueness of ." Trans. New York Acad. Sci. 31, 656-675, 1969.Gewirtz, A. "Graphs with Maximal Even Girth." Canad. J. Math. 21, 915-934, 1969.Godsil, C. and Royle, G. "Witt Design on 23 Points." §10.11 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 241-242, 2001.

## Cite this as:

Weisstein, Eric W. "Gewirtz Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GewirtzGraph.html