Golomb Graph

Author

Eric W. Weisstein
October 23, 2022

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

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

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

Embeddings

GraphData["GolombGraph","StandardName"]

Primary

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

All

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

Colored

GraphData[gn="GolombGraph","Graph","All"]/.g_Graph:>Annotate[g,{
VertexStyle->MapIndexed[#2[[1]]->{Red,Yellow,Green,Blue}[[#]]&,GraphData[gn,"MinimumVertexColoring"]],
VertexSize->{"Scaled",.03},
ImageSize->Small}]

Planar

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

Triangle exterior planar construction

ShowLabeledGraph[g4=ChangeVertices[g3,Join[4/(Sqrt[3])Table[Through[{Cos,Sin}[-2 π n/3+π/2]],{n,0,2}],Table[Through[{Cos,Sin}[-2 π n/6+π/2]],{n,0,5}],{{0,0}}]],AspectRatio->Automatic]

Symmetric construction

v=Flatten[{RootReduce[Table[{(1/6),((Sqrt[11])/6)}.RotationMatrix[2 n Pi/3],{n,0,2}]],Table[{1,0}.RotationMatrix[n Pi/3],{n,0,5}],{{0,0}}},1]

e=UnitEdges[v]

g=Graph[Range[Length[v]],e,VertexCoordinates->v]

RecognizeGraph[g]

Circulant

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

Halin

GraphData["GolombGraph","Halin"]

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

LCF

GraphData["GolombGraph","LCF"]

GraphData["GolombGraph","LCFSignature"]

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

UnitDistance

GraphData["GolombGraph","UnitDistance"]

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

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData["GolombGraph","Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

{"GolombGraph",l=FindSubgraphUnitDistanceEmbedding[GraphData["GolombGraph"],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData["GolombGraph","Matchstick"]

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

MinimalCrossing

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

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

Default embedding

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

e[l__]:=Sequence@@Partition[{l},2,1]

v={{0,0},{1/2,0},{1,0},{1,1},{1/2,1},{0,1},{0,1/2},{1/4,1/2},{1/2,1/2},{3/4,1/2}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,6,8,1,9,6],e[3,10,9,8,7,5,8,2,7],{4,10}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData["GolombGraph"],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData["GolombGraph"],TimeConstraint->60]//AbsoluteTiming

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["GolombGraph"],"CrossingNumber"->-1],-1-Pi/2]

RecognizeGraph[g]

v={{0,0},{1,0},{1,1},{3/4,1},{1/2,1},{1/4,1},{0,1},{1/2,1/2},{1/2,3/2},{1/2,2}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,10,7,1,8,2],e[7,6,5,4,3],e[8,5,9,10],e[6,9,4],e[7,9,3]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData["GolombGraph"]]

Tally[ReverseSort[Length/@faces]]

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

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{,}

RecognizeGraph/@gs

Tutte embedding construction 5 #1

GraphPlot[RotateGraph[,-2Pi/5]]

h=v[[4,2]]//FullSimplify

v=Join[UnitCirclePoints[5],{#/2,h}&/@{-1,0,1},{{0,-1/4},{0,5/8}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,9,5],e[4,6,7,8,2,10,4],e[9,7,10,3],e[6,10,8]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Tutte embedding construction 3 #1

GraphPlot[]

v=Join[{{0,0}},CirclePoints[Csc[Pi/3]/2,3],CirclePoints[Csc[Pi/3]/4,3]];
v=Join[v,Table[RotationMatrix[2Pi i/3].Mean[v[[{5,7}]]],{i,0,2}]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[2,3,4,2,5,1,10],e[5,9,6,10,7,8,5],e[4,7,1,9],e[3,6,1,8]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Tutte embedding construction 3 #2

GraphPlot[RotateGraph[,-2Pi/3]]

v=Join[{{-1,0},{1,0},{0,Sqrt[3]},{-1/4,1/4},{0,1/4},{1/2,1/4},{0,1/2},{-1/4,3/4},{0,3/4},{1/4,3/4}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,1,4,5,6,2],e[1,8,3,10,6,3,9,7,5],e[8,9,10],{4,7}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

3D default

Graph3D[GraphData["GolombGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["GolombGraph","Polyhedral"]

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

Graphics3D[{FaceForm[Green,Red],GraphData["GolombGraph","Polyhedron"]}]

3D Canonical

GraphData["GolombGraph","Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData["GolombGraph","Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData["GolombGraph"],1]}]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->100,MaxIterations->50000,PrecisionGoal->20,"ProgressInterval"->500,"TangentFactor"->1/10,"PlanarFactor"->1/10,Debug->True])//Timing

SimplePolyhedronQ[can]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

Properties

Missing

GraphData["GolombGraph","Missing"]

Graph["GolombGraph"]//InputForm

g=Graph[{{{1, 2}}, {{1, 3}}, {{1, 4}}, {{2, 3}}, {{2, 6}}, {{3, 8}}, {{4, 5}}, {{4, 9}}, {{4, 10}}, {{5, 6}}, {{5, 10}}, 
  {{6, 7}}, {{6, 10}}, {{7, 8}}, {{7, 10}}, {{8, 9}}, {{8, 10}}, {{9, 10}}}, 
 {{{0.1667, 0.5528}}, {{0.3954, -0.4207}}, {{-0.562, -0.132}}, {{1., 0.}}, {{0.5, -0.866}}, {{-0.5, -0.866}}, 
  {{-1., 0.}}, {{-0.5, 0.866}}, {{0.5, 0.866}}, {{0., 0.}}}];

EdgeChromaticNumber

EdgeChromaticNumber[g]//Timing

Degrees[g]//Max

EdgeConnectivity

EdgeConnectivity[g]//Timing

Faces

g=ToCombinatoricaGraph[]

v=ToCommonEdges[g,Graph["GolombGraph"]]

ShowLabeledGraph[g2=ChangeVertices[Graph["GolombGraph"],v]]

Faces[g2]

Length[%]

GraphData

GraphDataClasses

GraphClassString["GolombGraph"]

GraphDataString

GraphDataString[g,
"StandardName"->"GolombGraph",
"Name"->"Golomb graph",
"Classes"->{"UnitDistance"},
"Information"->"GolombGraph",
Debug->True,
TimeConstraint->300
]

GetGraphData[#,"File"]&/@{"HarborthGraph","MoserSpindle"}