Goddard-Henning Graph

Author

Eric W. Weisstein
September 2, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Goddard-HenningGraph.nb.

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

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

Theorem: domination numbers of planar graphs with diameter d

d==2

Select[Intersection[GraphData["Planar"],GraphData["DominationNumber","Defined"]],GraphData[#,"Diameter"]==2&&GraphData[#,"DominationNumber"]>2&]

γ≤2 except for (Subscript[G, 9])

G9 is the  unique planar graph of diameter two with domination number 3

Henning and Yeo 2013, Theorem 6.1, p. 55-56

Goddard, W., Henning, M.A.: Domination in planar graphs with small diameter. J. GraphTheory 40, 1–25 (2002)

d==3

Select[Intersection[GraphData["Planar"],GraphData["DominationNumber","Defined"]],GraphData[#,"Diameter"]==3&&GraphData[#,"DominationNumber"]>10&]

Select[Intersection[GraphData["Planar"],GraphData["DominationNumber","Defined"]],GraphData[#,"Diameter"]==3&&GraphData[#,"DominationNumber"]==10&]

Embeddings

GraphData["GoddardHenningGraph","StandardName"]

Primary

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

All

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

Planar

GraphData["GoddardHenningGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["GoddardHenningGraph"]]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Tutte embeddings

<<IGraphM`

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

Tally[ReverseSort[Length/@faces]]

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

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

Tutte embedding construction 4 #1 (Goddard-Henning paper)

GraphPlot[RotateGraph[]]

g=Graph[Range[9],UndirectedEdge@@@Sort[Sort/@Join[
Partition[{1,2,3,4},2,1,1],
Partition[{7,3,6,2,5,1,8,4},2,1,1],
{{7,9},{9,5},{6,9},{9,8}}
]],VertexCoordinates->Join[CirclePoints[4],CirclePoints[{.35,0},4],{{0,0}}]]

RecognizeGraph@g

Tutte embedding construction 4 #2

GraphPlot[RotateGraph[,-Pi/4]]

Mean[v[[{7,3}]]]

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

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

RecognizeGraph[g]

Tutte embedding construction 3

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

RegionIntersection[Line[v[[{2,7}]]],Line[{v[[6]],{v[[6,1]],1}}]]

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

RecognizeGraph[g]

LCF

GraphData["GoddardHenningGraph","LCFSignature"]

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

UnitDistance

GraphData["GoddardHenningGraph","UnitDistance"]

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

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

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

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

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

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

gs=UniqueEmbeddings[l]

RotateGraph[,{285,6}]

gs={,,,,,,,};

Matchstick

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

Default embedding

g=Graph@GraphData["GoddardHenningGraph","Edges"]

g2=System`Graph[EdgeList[g],VertexLabels->"Name"]

Round[20ToCommonEdges[g2,g]/1.634536145576477`]/10

3D All

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

3D Polyhedron

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

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

3D Canonical

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

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

3D Polyhedron construction

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

Graphics3D[poly2=Polyhedron[Normalize/@poly[[1]],poly[[2]]]]

(can=FindCanonicalPolyhedron[poly2,WorkingPrecision->1000,MaxIterations->5000,PrecisionGoal->20])//Timing

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

SimplePolyhedronQ[can]

(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]

GraphData

file=OpenWrite["~/GoddardHenningGraph.m"]

WriteString[file,GraphDataString[g,
"StandardName"->"GoddardHenningGraph",
"Name"->"Goddard\[Hyphen]Henning graph",
Debug->True
]]

Close[file]