Klein Graph

Author

Eric W. Weisstein
October 18, 2018

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

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

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

Embeddings

Default

GraphData["KleinGraph"]//StyleGraphs

All

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

LCF

GraphData["KleinGraph","LCFSignature"]

GraphData["KleinGraph","|HC|"]

GraphData["KleinGraph","LCFNotations"]

LCFGraph@@@%[[2]]

i=GraphData["KleinGraph","AllImages"];

Length[lcf=Get["~/"<>GraphNameToFileName[g]<>"-Partial"]]

sig=Tally[lcf[[All,2]]]

nice=Select[lcf,Last[#]>2&]

GraphicsGrid[{i[[;;4]],i[[5;;7]],i[[8;;11]],i[[12;;15]]},ImageSize->500]

GraphicsRow[{,,,},Spacings->-20,ImageSize->400]

LCFCycleSearch["KleinGraph",10^5]//Timing

LCFCycleSearch["KleinGraph",10^6]//Timing

Hyperbolic Construction

Graphics[HyperbolicTiling[7,3]]

p=Select[First/@HyperbolicTilingVertices[7,3],Norm[#]<.82&];
Graphics[MapIndexed[{{Red,PointSize[.015],Point[#]},Text[First[#2],#+.035]}&,p]]

Flatten[Join[
{Partition[{9,10,16,18,24,23,17,15},2,1,1]},
Partition[#,2,1]&/@{{20,22,18},{30,28,24}}],1]

ShowLabeledGraph[g=Graph[List/@Flatten[Join[
{
Partition[{9,10,16,18,24,23,17,15},2,1,1]},
{{{12,14},{22,26},{28,32},{27,29},{19,21},{7,11},{1,5},{4,6}}},
{{{}}}
Partition[#,2,1]&/@{{20,22,18},{30,28,24},{31,27,23},{25,21,17},{13,11,15},{3,5,9},{2,6,10},{8,12,16}}],1],List/@p]]

M[g]

Construction

Cycles

ShortCycles[edgelist_]:=Union[Table[With[
{k=ShortestPath[FromUnorderedPairs[Drop[edgelist,{n}]],edgelist[[n,1]],edgelist[[n,2]]]},First[Sort[Flatten[Table[{RotateLeft[k,r],RotateLeft[Reverse[k],r]},{r,Length[k]}],1]]]],{n,Length[edgelist]}]]
CompleteShortCycles[g_Graph]:= Module[{orphans ,edgelist=Edges[g]},
orphans=Split[Sort[Split[
Sort[Sort/@Flatten[Partition[#,2,1,1]&/@ShortCycles[edgelist],1]]]],Length[#1]==Length[#2]&];
If[Length[orphans]==1,ShortCycles[edgelist],If[Length[orphans]==2,Sort[Join[ShortCycles[edgelist],With[{vert=Union[Flatten[Map[First,First[orphans]]]]},ShortCycles[Map[First,First[orphans]]/.Thread[vert ->Range[Length[vert]]]]/.Reverse/@Thread[vert ->Range[Length[vert]]]]]],$Failed]]]

GraphInverse[g_]:=With[{gg=CompleteShortCycles[g]},
Flatten[Table[If[Length[Intersection[gg[[a]],gg[[b]]]]==2,{a,b},Sequence@@{}],{a,1,Length[gg]-1},{b,a+1,Length[gg]}],1]]

KleinGraph = Module[{e=GraphInverse[Graph["F056B"]]},Graph[List/@e,CircularEmbedding[Max[Flatten[e]]]]]

ShowGraph[KleinGraph]

distanceregular.org

g=DistanceRegularGraph["klein"]

RecognizeGraph[g]

VertexCount[g]

GraphDiameter[g]//Timing

RegularParameters[g]//Timing

DistanceRegularGraphQ[g]//Timing

IntersectionArray[g]//Timing

IntegerSpectrum[g]//SpectrumForm

GroupOrder[GraphAutomorphismGroup[g]]

HamiltonianGraphQ[g]

KleinDistance2Graph

DistanceGraph[GraphData["KleinGraph"],2]//RecognizeGraph

Diameter[Graph["KleinGraph"]]

Embeddings

LCFCycleSearch["KleinDistance2Graph",10^5]//Timing

LCFCycleSearch["KleinDistance2Graph",10^6]//Timing

LCFCycleSearch["KleinDistance2Graph",5 10^6]//Timing

GraphData

GraphClassString

GraphClassString["KleinGraph"]

GraphDataTable

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

GraphDataString

GraphDataString[KleinGraph,
"Name"->"Klein graph",
"StandardName"->"KleinGraph",
"Classes"->{"DistanceRegular"},
"Vertices"->None,
"Skip"->{"Perfect"},
Debug->True,
TimeConstraint->60
]

file=OpenWrite["klein2.m"]

WriteString[file,GraphDataString[d2klein,
"Name"->"distance-2 graph of the Klein graph",
"StandardName"->"KleinDistance2Graph",
"Classes"->{"DeterminedBySpectrum"},
"Skip"->{"Perfect"},
Debug->True,
TimeConstraint->60
]]

Close[file]