TOPICS
Search

Goethals-Seidel Graphs


A number of strongly regular graphs of several types derived from combinatorial design were 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://www.win.tue.nl/~aeb/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.distanceregular.org/graphs/goethalsseidel.html.Goethals, J.-M. and Seidel, J. J. "Strongly Regular Graphs Derived from Combinatorial Designs." Can. J. Math. 22, 597-514, 1970.

Cite this as:

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

Subject classifications