Shrikhande Graph

Author

Eric W. Weisstein
August 6, 2023

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

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["ShrikhandeGraph","StandardName"]

GraphData["ShrikhandeGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ShrikhandeGraph","EdgeList"]]

Default embedding

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

v=Join[CirclePoints[4],CirclePoints[{1/2,Pi/2},4],CirclePoints[{1/2-1/8,Pi/2},4],CirclePoints[1/4,4]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,4},1,8,2,5,3,6,4,7,1,12,2,9,3,10,4,11,1],e[7,12,5,10,7],e[7,13,14,5,15,16,7],e[6,15,14,8,13,16,6,9,8,11,6],e[15,11,14],e[16,9,13],e[14,10,13],e[15,12,16]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

RecognizeGraph[g]

v=Join[CirclePoints[1,8],CirclePoints[x,8]];

Solve[v[[6,2]]==v[[13,2]],x]//FullSimplify

v=Join[CirclePoints[1,8],CirclePoints[Tan[(π/8)],8]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,8},1,10,3,1,7,16,1],e[7,14,5,7],e[5,12,3,5],e[6,13,4,6],e[4,11,2,4],e[6,8,15,6],e[8,2,9,8],e[16,13,10,15,12,9,14,11,16,14,12,10,16],e[15,13,11,9,15]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

g0=Annotate[LabelGraph@,VertexLabelStyle->Large]

VertexDegree[g0]

EdgeList[g0]

%108[[Position[%108,14][[All,1]]]]

v=Join[CirclePoints[1,8],CirclePoints[Tan[(π/8)],8]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,8},1],e[14,11,16,13,4,15,12,1,10],e[12,14],e[6,9,12],e[10,13,2,11,5,14,8,9,3,12,6,15,1],e[5,16,7,10,15],e[8,11],e[3,14,9],{2,16},e[4,11,1],{7,13}},VertexCoordinates->v,VertexLabels->Automatic,VertexLabelStyle->Medium]

VertexDegree[g]

RecognizeGraph@g

gs=UnlabelGraph/@{,,,}

Degenerate

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

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

Bilateral

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

Circular

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

Toroidal

GraphData["ShrikhandeGraph","Graph","Torus"]//StyleGraphs

Planar

GraphData["ShrikhandeGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

(g=MinimalCrossingGraph[GraphData["ShrikhandeGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

GraphData["ShrikhandeGraph","Polyhedral"]

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["ShrikhandeGraph","Circulant"]

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

Line graph

GraphData["ShrikhandeGraph","Line"]

LineGraphQ[GraphData["ShrikhandeGraph"]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "ShrikhandeGraph"&]

RootGraph[GraphData["ShrikhandeGraph"]]

Halin

GraphData["ShrikhandeGraph","Halin"]

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

Rigid

GraphData["ShrikhandeGraph","Rigid"]

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

Flexible

GraphData["ShrikhandeGraph","Flexible"]

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

LCF

GraphData["ShrikhandeGraph","LCF"]

GraphData["ShrikhandeGraph","HamiltonianCycleCount"]

GraphData["ShrikhandeGraph","LCFSignature"]

GraphData["ShrikhandeGraph","LCFNotations"]

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

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

LCF compute all

Length[FindHamiltonianCycle[GraphData["ShrikhandeGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["ShrikhandeGraph"],All])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

Length[%]

(gs=Flatten[{
(* all LCF's with order >2, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFGraph@#,#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-2 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,2}]]}])//Timing

Length[gs]

UnitDistance

GraphData["ShrikhandeGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

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

g=LabelGraph@RotateGraph[,{16,13}]

DegenerateGraphEmbeddingTypes[g]

UnitDistanceGraphEmbeddingQ[g]

EdgeLengths[g]

EdgeList[g]

(degenerate)

LabelGraph@RotateGraph[,{11,6}]

LabelGraph@RotateGraph[,{6,9}]

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["ShrikhandeGraph","Matchstick"]

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

3D default

Graph3D[GraphData["ShrikhandeGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ShrikhandeGraph","Polyhedral"]

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

Matrices

GraphicsRow[GraphMatrixPlot[GraphData["ShrikhandeGraph"]]]

Construction

By hand

http://www.win.tue.nl/~aeb/drg/recta/6q/n6.002

ShrikhandeGraph (http://www.win.tue.nl/~aeb/drg/graphs/Shrikhande.html)

v=1+{{1,2,3,4,5,6},{0,2,6,7,8,9},{0,1,3,7,10,11},{0,2,5,10,12,13},{0,5,6,11,14,15},{0,3,4,8,12,14},{0,1,4,9,13,15},{1,2,8,11,12,15},{1,5,7,9,12,14},{1,6,8,10,13,14},{2,3,9,11,13,14},{2,4,7,10,14,15},{3,5,7,8,13,15},{3,6,9,10,12,15},{4,5,8,9,10,11},{4,6,7,11,12,13}}

GraphPlot[Rule@@@Edges[g=FromAdjacencyLists[v]]]

Wikipedia

ShowGraph[g=SVGToGraph[Import["http://upload.wikimedia.org/wikipedia/commons/7/76/Shrikhande_graph_symmetrical.svg","XML"]]]

RecognizeGraph[g]

ToCommonEdges[g,Graph["ShrikhandeGraph"]]/560.

GetGraphData["ShrikhandeGraph","File"]

distanceregular.org

g=DistanceRegularGraph["http://www.distanceregular.org/graphdata/shrikhande.am"]

RecognizeGraph[g]

VertexCount[g]

GraphDiameter[g]//Timing

RegularParameters[g]//Timing

DistanceRegularGraphQ[g]//Timing

IntersectionArray[g]//Timing

IntegerSpectrum[g]//SpectrumForm

GroupOrder[GraphAutomorphismGroup[g]]

HamiltonianGraphQ[g]

Toroidal

GraphData["ShrikhandeGraph","Toroidal"]

s=Sqrt[3]/2;
v=Join[
Table[{i s,0},{i,0,6,2}],
Sequence@@Table[{i s,y},{i,2,4,2},{y,-1,1,2}],
Sequence@@Table[{i s,y},{i,1,5,2},{y,-1/2,1/2}],
Table[{3s,i 3/2},{i,-1,1,2}]
];

e=Select[Subsets[Range[Length[v]],{2}],EuclideanDistance@@v[[#]]==1&]

GraphData["ShrikhandeGraph",{"V","E"}]

GraphData["TorusTriangulation",16]

Wrong

g0=Graph[Range[Length[v]],UndirectedEdge@@@Join[e,{{9,14},{4,5},{1,8},{1,4},{13,16},{7,16},{6,7},{6,15},{10,15},{4,10},{4,15},{1,16},{8,9},{5,14},{1,13}}],VertexCoordinates->v,VertexLabels->"Name"]

Through[{VertexCount,EdgeCount}[g]]

VertexDegree[g]

r0=RecognizeGraph[g0]

ToCommonEdges[g0,GraphData[r0]]

GetGraphData[r0,"File"]

Correct

g=Graph[Range[Length[v]],UndirectedEdge@@@Join[e,{
{1,16},{8,9},{5,14},{4,15},
{1,15},{7,10},{6,13},{4,16},
{1,7},{1,8},{4,6},{4,5},{15,16},{9,14},{10,13}
}],VertexCoordinates->v,VertexLabels->"Name"]

Through[{VertexCount,EdgeCount}[g]]

VertexDegree[g]

r=RecognizeGraph[g]

ToCommonEdges[g,GraphData[r]]

GraphData

GraphClassString

GraphClassString["ShrikhandeGraph"]

GraphDataTable

TableForm[GraphDataTable["ShrikhandeGraph",x],TableDepth->2]//TraditionalForm

GraphDataString

GraphDataString[g,{"ShrikhandeGraph","Shrikhande graph","ShrikhandeGraph"},TimeConstraint->60,Vertices->None,Debug->True]