Soicher Graphs

Author

Eric W. Weisstein
April 12, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/SoicherGraphs.nb.

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

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

Source

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

Embeddings

<<MathWorld`Graphs`

{"Soicher", 2}

GraphData[{"Soicher",2},"StandardName"]

Primary

GraphData[{"Soicher",2}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Soicher",2},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Soicher",2},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Soicher",2},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Soicher",2},"Edges"]

v={};
g=Graph[Range[Length[v]],Sort[Sort/@UndirectedEdge@@@{}],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"Soicher",2},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Soicher",2},"Graph","Degenerate"]

Bilateral

GraphData[{"Soicher",2},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Soicher",2},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"Soicher",2},"|HC|"]

Length[hc=FindHamiltonianCycle[GraphData[{"Soicher",2}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Soicher",2}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"Soicher",2},"Planar"]

GraphData[{"Soicher",2},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Soicher",2},{"RCN","CN"}]

GraphData[{"Soicher",2},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Soicher",2}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Soicher",2}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Soicher",2}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Soicher",2},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Soicher",2}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Soicher",2},"Circulant"]

GraphData[{"Soicher",2},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Soicher",2},"Halin"]

GraphData[{"Soicher",2},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Soicher",2},"Rigid"]

GraphData[{"Soicher",2},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Soicher",2},"Flexible"]

GraphData[{"Soicher",2},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Soicher",2},"LCF"]

GraphData[{"Soicher",2},"HamiltonianCycleCount"]

GraphData[{"Soicher",2},"LCFSignature"]

GraphData[{"Soicher",2},"LCFNotations"]

GraphData[{"Soicher",2},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Soicher",2}],TimeConstraint->120]

LCF compute 10^3

Tally[(lcf=LCF[GraphData[{"Soicher",2}],10^3])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

UnitDistance

GraphData[{"Soicher",2},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Soicher",2}],Debug->True]//Timing

GraphData[{"Soicher",2},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Soicher",2},"VertexList"],GraphData[{"Soicher",2},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Soicher",2},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Soicher",2}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"Soicher",2},"Matchstick"]

GraphData[{"Soicher",2},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Soicher",2},"Edges"]]

3D All

GraphData[{"Soicher",2},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Soicher",2},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Soicher",2},"Polyhedral"]

GraphData[{"Soicher",2},"Graph",{"3D","Polyhedron"}]

{"Soicher", 3}

GraphData[{"Soicher",3},"StandardName"]

Primary

GraphData[{"Soicher",3}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Soicher",3},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Soicher",3},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Soicher",3},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Soicher",3},"Edges"]

v={};
g=Graph[Range[Length[v]],Sort[Sort/@UndirectedEdge@@@{}],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"Soicher",3},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Soicher",3},"Graph","Degenerate"]

Bilateral

GraphData[{"Soicher",3},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Soicher",3},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"Soicher",3},"|HC|"]

Length[hc=FindHamiltonianCycle[GraphData[{"Soicher",3}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Soicher",3}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"Soicher",3},"Planar"]

GraphData[{"Soicher",3},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Soicher",3},{"RCN","CN"}]

GraphData[{"Soicher",3},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Soicher",3}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Soicher",3}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Soicher",3}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Soicher",3},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Soicher",3}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Soicher",3},"Circulant"]

GraphData[{"Soicher",3},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Soicher",3},"Halin"]

GraphData[{"Soicher",3},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Soicher",3},"Rigid"]

GraphData[{"Soicher",3},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Soicher",3},"Flexible"]

GraphData[{"Soicher",3},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Soicher",3},"LCF"]

GraphData[{"Soicher",3},"HamiltonianCycleCount"]

GraphData[{"Soicher",3},"LCFSignature"]

GraphData[{"Soicher",3},"LCFNotations"]

GraphData[{"Soicher",3},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Soicher",3}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Soicher",3}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

UnitDistance

GraphData[{"Soicher",3},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Soicher",3}],Debug->True]//Timing

GraphData[{"Soicher",3},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Soicher",3},"VertexList"],GraphData[{"Soicher",3},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Soicher",3},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Soicher",3}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"Soicher",3},"Matchstick"]

GraphData[{"Soicher",3},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Soicher",3},"Edges"]]

3D All

GraphData[{"Soicher",3},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Soicher",3},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Soicher",3},"Polyhedral"]

GraphData[{"Soicher",3},"Graph",{"3D","Polyhedron"}]

Construction

GraphData["Soicher*"]

gap> LoadPackage("grape");;
gap> soicher1:=EdgeOrbitsGraph(...);
gap> UndirectedEdges(soicher1);
gap: cannot extend the workspace any more
%

g1=XXX

g2=DistanceRegularGraph["soicher2nd"]

g3=DistanceRegularGraph["soicher3rd"]

Properties

2nd

VertexCount[g2]

GraphDiameter[g2]

RegularParameters[g2]//Timing

<<IGraphM`

IGIntersectionArray[g2]

IntegerSpectrum[g2]//SpectrumForm

DistanceRegularGraphQ[g2]//Timing

DistanceTransitiveGraphQ[g2]//Timing

3rd

VertexCount[g3]

GraphDiameter[g3]

RegularParameters[g3]//Timing

<<IGraphM`

IGIntersectionArray[g3]

IntegerSpectrum[g3]//SpectrumForm

DistanceRegularGraphQ[g3]//Timing

DistanceTransitiveGraphQ[g3]//Timing

GraphData

GraphDataClassString

GraphDataClassString[g]

GraphDataString

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

WriteString[file,GraphDataString[g2,
"StandardName"->{"Soicher",2},
"Name"->"seconod Soicher graph",
"Information"->"SoicherGraphs",
"Embeddings"->{},
"Skip"->{"Arboricity","BurningNumber","Chord","ChordlessCycle","ChordlessCycles","Chords","ChromaticNumber","ComplementOddChordlessCycle","ComplementOddChordlessCycles","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","CrossingNumber","Cycles","CyclePolynomial","CycleSignature","DominatingSet","DominatingSets","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumFlowMatrix","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","OddChordlessCycles","PathPolynomial","Paths","RadioLabeling","RadioLabelings","RadioNumber","RectilinearCrossingCount","ResistanceMatrix","Skewness","StronglyPerfect","UnitDistance","Thickness"},
TimeConstraint->10
]]

WriteString[file,GraphDataString[g3,
"StandardName"->{"Soicher",3},
"Name"->"third Soicher graph",
"Information"->"SoicherGraphs",
"Embeddings"->{},
"Skip"->{"Arboricity","BurningNumber","Chord","ChordlessCycle","ChordlessCycles","Chords","ChromaticNumber","ComplementOddChordlessCycle","ComplementOddChordlessCycles","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","CrossingNumber","Cycles","CyclePolynomial","CycleSignature","DominatingSet","DominatingSets","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumFlowMatrix","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","OddChordlessCycles","PathPolynomial","Paths","RadioLabeling","RadioLabelings","RadioNumber","RectilinearCrossingCount","ResistanceMatrix","Skewness","StronglyPerfect","UnitDistance","Thickness"},
TimeConstraint->10
]]

Close[file]