Hoffman Graph

Author

Eric W. Weisstein
November 10, 2022

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

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

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

Embeddings

Names

GraphData["HoffmanGraph","StandardName"]

GraphData["HoffmanGraph","StandardNames"]

Primary

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

All

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

Embedding types

GraphDataEmbeddings[GraphData["HoffmanGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData["HoffmanGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData["HoffmanGraph"],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HoffmanGraph"],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HoffmanGraph"],TimeConstraint->5 3600])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData["HoffmanGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

g=RotateGraph[MinimalCrossingGraph[GraphData["HoffmanGraph"],"CrossingNumber"->cn]]

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

GraphPlot@RotateGraph[,Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["HoffmanGraph","Circulant"]

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

Halin

GraphData["HoffmanGraph","Halin"]

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

LCF

GraphData["HoffmanGraph","LCF"]

GraphData["HoffmanGraph","LCFSignature"]

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

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

LCF compute

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

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

gs=LCFGraph@@@lcf//StyleGraphs

gs=Join[With[{g=BilateralLCFEmbedding[#]},If[MissingQ[g],#,g]]&/@LCFGraph@@@DeleteCases[lcf,{_,1}],DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]]

Length[gs]

UnitDistance

GraphData["HoffmanGraph","UnitDistance"]

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

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

Matchstick

GraphData["HoffmanGraph","Matchstick"]

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

3D default

Graph3D[GraphData["HoffmanGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["HoffmanGraph","Polyhedral"]

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

Properties

FastIsomorphicQ@@(Graph/@{"Q4","HoffmanGraph"})

SpectrumForm/@(GraphData[#,"Spectrum"]&/@{"Q4","HoffmanGraph"})//ColumnForm//TraditionalForm

GraphData

GraphClassString

GraphClassString["HoffmanGraph"]

Construction

HoffmanGraph:=Module[{d=(({{1, 1, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 0, 0, 1, 1}, {1, 0, 0, 0, 1, 1, 1, 0}, {0, 1, 0, 0, 1, 1, 0, 1}, {0, 0, 1, 0, 1, 0, 1, 1}})),z=ConstantArray[0,{8,8}]},
AdjacencyGraph[ArrayFlatten[{{z,d},{Transpose[d],z}}]]]

HoffmanGraph

RecognizeGraph@%