mathworld.wolfram.com

Gewirtz Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Fri Oct 10 2003
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

GewirtzGraph

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 strongly regular graph with parameters (nu,k,lambda,mu)=(56,10,0,2). 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 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 10^12^(35)(-4)^(20) (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 80640.

It is distance-regular with intersection array {10,9;1,2} 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.

abciluabdfrsabejopabgmnqacdghpacfjntackmos
ademtuadjklqaefgikaehlnsafhoquaglortahijmr
aipqstaknprubcdeknbchjqsbcmprtbdgijtbdhlmo
beflqtbeghrubfhinpbfjkmubgklpsbikoqrbnostu
cdfimqcdjorucefpsucegjlmcehiotcfhklrcginrs
cgkqtuclnopqdegoqsdeilprdfglnudfkoptdhiksu
dhnqrtdjmnpsefmnorehkmpqeijnquejkrstfghmst
fgjpqrfijlosghjknogimopuhjlptuiklmntlmqrsu

See also

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

Explore with Wolfram|Alpha

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 g(2,2,10,56)." 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

Subject classifications