Sylvester Graph

Author

Eric W. Weisstein
October 31, 2023

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

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["SylvesterGraph","StandardName"]

GraphData["SylvesterGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["SylvesterGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

Perspective

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

Perspective construction

GraphData["SylvesterGraph","Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData["SylvesterGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["SylvesterGraph","Circulant"]

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

Complement graph

GraphData["SylvesterGraph","ComplementGraph","Name"]

Line graph

GraphData["SylvesterGraph","Line"]

LineGraphQ[GraphData["SylvesterGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["SylvesterGraph"]]

Halin

GraphData["SylvesterGraph","Halin"]

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

Rigid

GraphData["SylvesterGraph","Rigid"]

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

Flexible

GraphData["SylvesterGraph","Flexible"]

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

LCF

GraphData["SylvesterGraph","LCF"]

GraphData["SylvesterGraph","HamiltonianCycleCount"]

GraphData["SylvesterGraph","LCFSignature"]

GraphData["SylvesterGraph","LCFNotations"]

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

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

lcf=LCFNotation/@{,,}

gs=NiceLCFGraphs[lcf,6]

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

LCF compute 10^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2|3}]

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

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

Length[gs]

LCF compute 5*^7

Tally[(lcf=LCF[GraphData["SylvesterGraph"],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2|3}]

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

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

Length[gs]

gs

LCFNotation/@gs

Cases[%,{_,6}]

gs=NiceLCFGraphs[{{{{-18,-10,-5},{-16,5,8},{-15,-4,10},{-8,7,16},{-18,-7,4},{-6,6,15}},6},{{{-18,-7,14},{-15,-10,4},{-14,-6,6},{-18,7,10},{-11,-7,15},{-4,7,11}},6},{{{-18,-5,10},{-15,5,13},{-13,-10,-5},{-18,5,14},{-10,10,15},{-14,-6,6}},6},{{{-18,-5,10},{-11,-8,5},{-15,-5,11},{-18,5,14},{-10,-6,6},{-14,8,15}},6}},4]

LCF compute all

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["SylvesterGraph",".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["SylvesterGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData["SylvesterGraph","Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

FindUnitDistanceEmbedding[GraphData["SylvesterGraph"],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["SylvesterGraph","Matchstick"]

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

3D default

Graph3D[GraphData["SylvesterGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["SylvesterGraph","Polyhedral"]

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

Construction

distanceregular.org

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