Goethals-Seidel Graphs

Author

Eric W. Weisstein
April 16, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Goethals-SeidelGraphs.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Goethals-SeidelGraphs.html.

©2021 Wolfram Research, Inc. except for portions noted otherwise

{"GoethalsSeidelBlockDesign", {k, r}} family from Theorem 2.4

Graphs

DeleteCases[Show[GraphData[#],PlotLabel->GraphData[#,"Name"]]&/@With[{class="GoethalsSeidelBlockDesign"},Sort[{Lookup[GraphData[#,"NotationRules"],class],#}&/@GraphData[class]][[All,2]]],_Show]

Special cases

With[{class="GoethalsSeidelBlockDesign"},TextGrid[Sort[{Lookup[GraphData[#,"NotationRules"],class],GraphData[#,"V"],#}&/@GraphData[class]],Dividers->All,Alignment->{{Left,Decimal,Left}}]]

Construction

Theorem 2.4 of [GS1970] in
J.-M. Goethals and J. J. Seidel, Strongly regular graphs derived from combinatorial designs, Can. J. Math. 22 (1970) 597-614. doi:10.4153/CJM-1970-067-9

Sage

https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.GoethalsSeidelGraph

data=Monitor[DeleteCases[Flatten[Table[{
{k,r},
{t,res}=SageEvaluate["graphs.GoethalsSeidelGraph("<>ToString[k]<>","<>ToString[r]<>").edges()"]//AbsoluteTiming;{t,If[res==="",$Failed,SageGraph[res]]}
},{k,7},{r,12}],1],{_,{_,$Failed}}],{k,r}];//Timing

data

cf=CanonicalForm[];//Timing

TextGrid[{#,VertexCount[#2],EdgeCount[#2],Flatten@RegularParameters[#2],RecognizeGraph[#2]}&@@@data,Dividers->All,Alignment->{{{Decimal},Left}}]

Cases[data,{in_,__,{}}:>in]

{{2,7},{2,11},{3,7},{5,11}}

<<IGraphM`

IGDistanceRegularQ/@data[[All,-1]]

"GoethalsSeidelGraph105" from Theorem 2.7

GraphData["StronglyRegular",105]

https://www.win.tue.nl/~aeb/graphs/srg/srgtab101-150.html
105-node graph: Aut L(3,4) on flags (rk 4) - Goethals & Seidel, unique by Coolsaet

J.-M. Goethals and J. J. Seidel, Strongly regular graphs derived from combinatorial designs, Can. J. Math. 22 (1970) 597-614. doi:10.4153/CJM-1970-067-9

GraphData["GoethalsSeidelGraph105","RegularParameters"]

Tally[Eigenvalues[SignedAdjacencyMatrix[GraphData["GoethalsSeidelGraph105"]]]]

SpectrumForm[Eigenvalues[SignedAdjacencyMatrix[GraphData["GoethalsSeidelGraph105"]]]]

(swapped signs?)

Distanceregular.org

https://www.distanceregular.org/graphs/goethalsseidel.html

Goethals-Seidel graph ≅ 2nd subconstituent of 2nd subconsituent of McLaughlin graph

g=DistanceRegularGraph["goethals-seidel"]

RecognizeGraph[g]

Properties

VertexCount[g]

GraphDiameter[g]

RegularParameters[g]

IntersectionArray[g]//Timing

<<IGraphM`

IGIntersectionArray[g]

IntegerSpectrum[g]//SpectrumForm

DistanceRegularGraphQ[g]//Timing

DistanceTransitiveGraphQ[g]//Timing

"GoethalsSeidelTacticalConfigurationn" graphs from Theorem 5.2  [missing no. 9]

TextGrid[Function[{no,n},{
no,
n,
Column[gs=GraphData["StronglyRegular",n]],
Column[Tally[Eigenvalues[SignedAdjacencyMatrix[GraphData[#]]]][[All,1]]&/@gs],
Column[t=Tally[GraphData[#,"Spectrum"]]&/@gs],
Column[Reverse@Tally[GraphData[#,"Spectrum"]][[All,2]]&/@gs]
}]@@@Transpose[{{2,3,6,7,9},{253,77,176,56,120}}],Dividers->All]

TextGrid[Table[With[{gn=GraphData[{"GoethalsSeidelTacticalConfiguration",n},"#"]/._GraphData:>Missing["NotAvailable"]},
{n,
gn,
Check[GraphData[gn,"Spectrum"]//SpectrumForm,Missing["NotAvailable"]],
Check[GraphData[gn,"RegularParameters"],Missing["NotAvailable"]]
}],{n,{2,3,6,7,9}}],Dividers->All]//Quiet//TraditionalForm

No. 9 (order 120) not in GraphData

Construction: "HigmanSimsGraph" graph from Theorem 5.3

TextGrid[{#,Tally[Round[Eigenvalues[N@SignedAdjacencyMatrix[GraphData[#]]]]]}&/@GraphData["StronglyRegular",100],Dividers->All]

-> HigmanSimsGraph

Construction: graph from Theorem 6.3 [missing]

GraphData["StronglyRegular",2048]

Not in GraphData

GraphData

GraphDataClassString

GraphDataClassString[g]

GraphDataString

{"GoethalsSeidelBlockDesign", {k, r}}

<<MathWorld`Graphs`

file=OpenAppend["~/new.m"]

Function[{k,r},WriteString[file,GraphDataString[SageGraph[SageEvaluate["graphs.GoethalsSeidelGraph("<>ToString[k]<>","<>ToString[r]<>").edges()"]],
"StandardName"->{"GoethalsSeidelBlockDesign",{k,r}},
"Name"->"("<>ToString[k]","<>ToString[r]<>")\[Hyphen]Goethals\[Hyphen]Seidel block design graph",
"Information"->"Goethals-SeidelGraphs",
"Embeddings"->{},
"Skip"->{"Arboricity","Chord","Chords","ChromaticNumber","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","Cycles","CyclePolynomial","CycleSignature","DominatingSet","DominatingSets","EdgeChromaticNumber","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","ComplementOddChordlessCycle","ComplementOddChordlessCycles","PathPolynomial","RadioLabeling","RadioLabelings","Skewness","VertexCover"},
TimeConstraint->10
]]]@@@{{5,11}};

Close[file]

105

file=OpenWrite["~/dr.m"]

WriteString[file,GraphDataString[g,
"StandardName"->"GoethalsSeidelGraph105",
"Name"->"105\[Hyphen]Goethals\[Hyphen]Seidel graph",
"Information"->"Goethals-SeidelGraphs",
"Embeddings"->{},
"Skip"->{"Arboricity","Chord","Chords","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","Cycles","CyclePolynomial","CycleSignature","DominatingSet","DominatingSets","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","ComplementOddChordlessCycle","ComplementOddChordlessCycles","PathPolynomial","RadioLabeling","RadioLabelings","Skewness"},
TimeConstraint->10
]]

Close[file]