Koolen-Riebeek Graph

Author

Eric W. Weisstein
March 17, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Koolen-RiebeekGraph.nb.

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

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

Source

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

Relation to Berlekamp-van Lint-Seidel Graph

halves=HalvedGraphs[GraphData["KoolenRiebeekGraph"]]

IsomorphicGraphQ@@halves

RecognizeGraph[halves[[1]]]

RecognizeGraph[GraphComplement[halves[[1]]]]

Embeddings

GraphData["KoolenRiebeekGraph","StandardName"]

Primary

GraphData["KoolenRiebeekGraph"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["KoolenRiebeekGraph","Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["KoolenRiebeekGraph","EdgeList"]]

Default embedding

GraphPlot@GraphData["KoolenRiebeekGraph","Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData["KoolenRiebeekGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["KoolenRiebeekGraph","Graph","Degenerate"]

Bilateral

GraphData["KoolenRiebeekGraph","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["KoolenRiebeekGraph","Graph","Circular"]//StyleGraphs

Circular construction

GraphData["KoolenRiebeekGraph","|HC|"]

Length[hc=FindHamiltonianCycle[GraphData["KoolenRiebeekGraph"],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["KoolenRiebeekGraph"],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

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

quad

Planar

GraphData["KoolenRiebeekGraph","Planar"]

GraphData["KoolenRiebeekGraph","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["KoolenRiebeekGraph",{"RCN","CN"}]

GraphData["KoolenRiebeekGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["KoolenRiebeekGraph"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["KoolenRiebeekGraph"],TimeConstraint->10])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["KoolenRiebeekGraph","Circulant"]

GraphData["KoolenRiebeekGraph","Graph","Circulant"]//StyleGraphs

Halin

GraphData["KoolenRiebeekGraph","Halin"]

GraphData["KoolenRiebeekGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["KoolenRiebeekGraph","Rigid"]

GraphData["KoolenRiebeekGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["KoolenRiebeekGraph","Flexible"]

GraphData["KoolenRiebeekGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["KoolenRiebeekGraph","LCF"]

GraphData["KoolenRiebeekGraph","HamiltonianCycleCount"]

GraphData["KoolenRiebeekGraph","LCFSignature"]

GraphData["KoolenRiebeekGraph","LCFNotations"]

GraphData["KoolenRiebeekGraph","Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData["KoolenRiebeekGraph"],TimeConstraint->60]

LCF compute 10^3

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

LCF compute 10^4

Tally[(lcf=LCF[GraphData["KoolenRiebeekGraph"],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Length[gs]

UnitDistance

GraphData["KoolenRiebeekGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["KoolenRiebeekGraph"],Debug->True]//Timing

GraphData["KoolenRiebeekGraph","Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["KoolenRiebeekGraph","VertexList"],GraphData["KoolenRiebeekGraph","EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["KoolenRiebeekGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData["KoolenRiebeekGraph","Matchstick"]

GraphData["KoolenRiebeekGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["KoolenRiebeekGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["KoolenRiebeekGraph","Polyhedral"]

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

Construction

g=DistanceRegularGraph["koolen-riebeek"]

RecognizeGraph[g]

Properties

VertexCount[g]

GraphDiameter[g]

RegularParameters[g]

IntersectionArray[g]//Timing

<<IGraphM`

IGIntersectionArray[g]

IntegerSpectrum[g]//SpectrumForm

DistanceRegularGraphQ[g]//Timing

DistanceTransitiveGraphQ[g]//Timing

GraphData

GraphDataClassString

GraphDataClassString[g]

GraphDataString

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

WriteString[file,GraphDataString[g,
"StandardName"->"KoolenRiebeekGraph",
"Name"->"Koolen-Riebeek graph",
"Information"->"Koolen-RiebeekGraph",
"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]