TOPICS
Search

Goethals-Seidel Graphs


The term "Goethals-Seidel graphs" is used in this work for strongly regular graphs of several types derived from combinatorial designs and identified by Goethals and Seidel (1970).

Theorem 2.4 of Goethals and Seidel (1970) identifies a family of strongly regular graphs corresponding to the existence of a block design with parameters v,b,k,r,lambda=1 and a Hadamard matrix of order r+1. Some of these graphs are implemented in the Wolfram Language as GraphData[{"GoethalsSeidelBlockDesign", {k, r}}].

Theorem 2.7 with r=5 leads to a strongly regular graph on 105 vertices with parameters (nu,k,lambda,mu)=(105,32,4,12) which is the second subconstituent of the second subconstituent of the McLaughlin graph. This graph is distance-regular but not distance-transitive with intersection array {32,27;1,12} and graph spectrum (-10)^(20)2^(84)32^1. This graph is implemented in the Wolfram Language as GraphData["GoethalsSeidelGraph105"].

Theorem 5.2 identifies a set of five strongly regular graphs having vertex degree equal to vertex count n summarized in the following table (where the graph spectrum uses the normal adjacency matrix, not the -1,1 versions appearing in Goethals and Seidel 1970).

numbernnamegraph spectrumregular parameters
2253(-26)^(22)2^(230)112^1(253,112,36,60)
377M22 graph(-6)^(21)2^5516^1(77,16,0,4)
6176(-18)^(21)2^(154)70^1(176,70,18,34)
756Gewirtz graph(-4)^(20)2^(35)10^1(56,10,0,2)
9120

Some of these graphs are implemented in the Wolfram Language as GraphData[{"GoethalsSeidelTacticalConfiguration", k}] using the numbering scheme above.

Theorem 5.3 identifies the strongly regular graph with vertices of degree 100 now known as the Higman-Sims graph.

Theorem 6.4 identifies a strongly regular graph on 2048 vertices.


See also

Distance-Regular Graph, Gewirtz Graph, Higman-Sims Graph, M22 Graph, McLaughlin Graph, Strongly Regular Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Parameters of Strongly Regular Graphs: 101-150 vertices." https://aeb.win.tue.nl/graphs/srg/srgtab101-150.html.Coolsaet, K. "The Uniqueness of the Strongly Regular Graph srg(105,32,4,12)." Simon Stevin 12, 707-718, 2005.DistanceRegular.org. "Goethals-Seidel graph." https://www.math.mun.ca/distanceregular/graphs/goethalsseidel.html.Goethals, J.-M. and Seidel, J. J. "Strongly Regular Graphs Derived from Combinatorial Designs." Can. J. Math. 22, 597-514, 1970.House of Graphs. Goethals-Seidel Graphs. K4,4, K5,5, K6,6, K7,7, Kneser K(8,2), Rook Complement Graph R(4,4), Square Graph C4, and Utility Graph K3,3.

Referenced on Wolfram|Alpha

Goethals-Seidel Graphs

Cite this as:

Weisstein, Eric W. "Goethals-Seidel Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Goethals-SeidelGraphs.html

Subject classifications