Hoffman-Singleton Graph

Author

Eric W. Weisstein
November 2, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Hoffman-SingletonGraph.nb.

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["HoffmanSingletonGraph","StandardName"]

GraphData["HoffmanSingletonGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["HoffmanSingletonGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData["HoffmanSingletonGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["HoffmanSingletonGraph","Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData["HoffmanSingletonGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["HoffmanSingletonGraph","Circulant"]

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

Complement graph

GraphData["HoffmanSingletonGraph","ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

RecognizeGraph@g

Line graph

GraphData["HoffmanSingletonGraph","Line"]

LineGraphQ[GraphData["HoffmanSingletonGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["HoffmanSingletonGraph"]]

Halin

GraphData["HoffmanSingletonGraph","Halin"]

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

Rigid

GraphData["HoffmanSingletonGraph","Rigid"]

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

Flexible

GraphData["HoffmanSingletonGraph","Flexible"]

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

LCF

GraphData["HoffmanSingletonGraph","LCF"]

GraphData["HoffmanSingletonGraph","HamiltonianCycleCount"]

GraphData["HoffmanSingletonGraph","LCFSignature"]

GraphData["HoffmanSingletonGraph","LCFNotations"]

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

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

g=LCFGraph[{{-24,-13,-5,7,16},{-22,-19,-8,-4,18},{-18,4,7,19,22},{-16,-5,8,15,24},{-22,-8,4,12,18},{-17,-6,5,14,23},{-16,-12,-4,8,24},{-24,-7,4,13,16},{-23,-15,-4,5,17},{-18,-14,-7,6,22}},5,-8]

LCF compute random

FindRandomLCFNotation[GraphData["HoffmanSingletonGraph"],TimeConstraint->120]//Timing//AbsoluteTiming

FindRandomLCFNotation[GraphData["HoffmanSingletonGraph"],TimeConstraint->3600]//Timing//AbsoluteTiming

LCF compute 10^5

Tally[(lcf=LCF[GraphData["HoffmanSingletonGraph"],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

LCF compute 10^6

Tally[(lcf=LCF[GraphData["HoffmanSingletonGraph"],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

LCF compute 10^7

Tally[(lcf=LCF[GraphData["HoffmanSingletonGraph"],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

LCF compute all

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["HoffmanSingletonGraph",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData["HoffmanSingletonGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData["HoffmanSingletonGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData["HoffmanSingletonGraph","Matchstick"]

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

3D default

Graph3D[GraphData["HoffmanSingletonGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["HoffmanSingletonGraph","Polyhedral"]

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

Properties

CrossingNumber

GraphData["HoffmanSingletonGraph","CrossingNumber"]

Exoo (RCN ≤ 872)

2019-05-12

QC (CN ≤ 863)

StringReplace[ExportString[GraphData["HoffmanSingletonGraph"],"Graph6"],">>graph6<<"|"\n"->""]

QC -r 1 -z 1000 -g 'qhcHKCPPG?_PA@?Oc@G@@O?cOGGGAK?Gc_?@@?AK?@?_O?`?G_HO??_a?_@G?a@@A?C@C@G?PH?C??GG?_@E?G?A@?_A?CG@?COCg?_?@@C?OC?H?C?P?_`?C?GAGA?H?AH?C_A??CA?O@?AGOO@??OGA?O@?AC_?A?G_H?H?C??GI?A?GA?Ca??G?a@@@?G?_@?P_?@?C_@C_'
New best found: 883, at seed: 1
New best found: 877, at seed: 3
New best found: 875, at seed: 10
New best found: 873, at seed: 14
New best found: 872, at seed: 60
New best found: 868, at seed: 73
New best found: 867, at seed: 320
New best found: 866, at seed: 616
New best found: 865, at seed: 6642
New best found: 863, at seed: 13583
New best found: 860, at seed: 19449
Current best soln: 860, at seed: 19449, current seed: 485000

Construction

Construction 1

p=ChangeVertices[CirculantGraph[5,{2}],Table[{Cos[#],Sin[#]}&[-2.Pi (i-1.75)/5],{i,5}]];

ShowLabeledGraph[p]

q=ChangeVertices[Cycle[5],Table[{Cos[#],Sin[#]}&[2.Pi(i-1+1/4)/5],{i,5}]];

ShowLabeledGraph[q]

g=GraphUnion[GraphUnion[5,p],GraphUnion[5,q]];
h=Graph[List/@Edges[g],List/@(Vertices[g]+Flatten[{Table[{0,0},{25}],
Table[{-2,-.2},{25}]},1])];

ShowLabeledGraph[h,AspectRatio->Automatic,
VertexColor->Red]

Table[{i,j,Mod[j+j  k,5]},{i,0,4},{j,0,4},{k,0,4}]

Table[Mod[j+j  k,5],{j,0,4},{k,0,4}]

Permutations[Range[4]]

pp[[2]]

pp=Append[#,0]&/@Permutations[Range[4]];
Table[
l=Flatten[Table[{5j+i+1,25+5k+1+Mod[j+j  k,5]+If[k==4,pp[[q,i+1]],0]},{i,0,4},{j,0,4},{k,0,4}],2];
(*Print[Table[Length@Select[l,MemberQ[#,n]&],{n,50}]];*)
hh=AddEdges[h,l];
Girth[hh],
{q,24}]

pp=Append[#,0]&/@Permutations[Range[4]];
Table[
l=Flatten[Table[{5j+i+1,25+5k+1+Mod[j+j  k,5]+If[k==4,pp[[q,j+1]],0]},{i,0,4},{j,0,4},{k,0,4}],2];
(*Print[Table[Length@Select[l,MemberQ[#,n]&],{n,50}]];*)
hh=AddEdges[h,l];
Girth[hh],
{q,24}]

Table[Mod[j+j  k,5],{i,2,2},{j,2,2},{k,0,4}]

l=Flatten[Table[{5j+i+1,25+5k+1+Mod[j+j  k,5]},{i,0,4},{j,0,4},{k,0,4}],2]

Table[Length@Select[l,MemberQ[#,n]&],{n,50}]

Construction 2

ArrayOfFive[g_,sgn_,ang_]:=Module[{i},GraphUnion[Sequence@@Table[ChangeVertices[g,Table[Through[{Cos,Sin}[sgn 2.Pi i/5+ang]],{i,5}]],{5}]]]

HoffmanSingletonGraph=LCFNotationMultiple[{{22,24,-22,23,24,-24,-23,22,-24,-22},{-18,-16,18,-17,-16,16,17,-18,16,18},{19,15,12,14,-12,13,-15,-14,-13,-19},{7,-5,-8,5,8,4,5,-7,-5,-4},{4,8,4,-6,-4,-7,-4,6,7,-8},{1,-1,1,-1,1,-1,1,-1,1,-1},{-1,1,-1,1,-1,1,-1,1,-1,1}},5]

HoffmanSingletonGraphConstruction:=HoffmanSingletonGraphConstruction=Module[{stars,cycles,g,v,i,j,k},stars=ArrayOfFive[CirculantGraph[5,{2}],-1,7Pi/10];
cycles=ArrayOfFive[Cycle[5],1,-3Pi/10];
v=Vertices[g=GraphUnion[stars,cycles]];
g=ChangeVertices[g,Join[Take[v,25],{-2,-.2}+#&/@Take[v,-25]]];
RadialEmbedding[AddEdges[g,Flatten[Table[{5j+i+1,26+5k+Mod[i+j k,5]},{i,0,4},{j,0,4},{k,0,4}],2]]]]

distanceregular.org

g=DistanceRegularGraph["http://www.distanceregular.org/graphdata/hoffmansingleton.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]