Cayley Graph

Author

Eric W. Weisstein
November 10, 2023

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

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

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

Additional Authors

Original figures by Todd Rowland
Cayley tetrahedron by Ed Pegg Jr.

Examples

c=Select[GraphData["CayleyGraph"],Head["CayleyGraph"/.GraphData[#,"NotationRules"]]=!=Missing&];

Take[c,10]

g=CayleyGraph[PermutationGroup[PermutationCycles/@("CayleyGraph"/.GraphData[#,"NotationRules"])[[1]]]]&/@Take[c,10]

VertexTransitiveQ/@g

Graph depends on choice of set

c1=CayleyGraph[PermutationGroup[{System`Cycles[{{1,2}}],System`Cycles[{{1,2,3,4}}]}]]

c2=CayleyGraph[PermutationGroup[{System`Cycles[{{1,2}}],System`Cycles[{{2,3}}],System`Cycles[{{3,4}}]}]]

c3=CayleyGraph[PermutationGroup[{System`Cycles[{{1,2,3}}],System`Cycles[{{2,3,4}}],System`Cycles[{{1,2,3,4}}],System`Cycles[{{1,2},{3,4}}]}]]

S_4

GroupGenerators[System`SymmetricGroup[4]]

GroupElements[System`SymmetricGroup[4]]

GraphicsRow[{c1,c2,c3},ImageSize->400]

RecognizeGraph/@UndirectedGraph/@{c1,c2,c3}

2 generators

Length[s=Subsets[GroupElements[SymmetricGroup[4]],{2}]]

Length[sets=FastIsomorphicSets[cg=CayleyGraph/@PermutationGroup/@s]]

cg[[sets[[All,1]]]]

Embeddings

<<MathWorld`Graphs`

GraphData["CayleyGraph*"]

24

{"CayleyGraph", {24, 1}}

Names

GraphData[{"CayleyGraph",{24,1}},"StandardName"]

GraphData[{"CayleyGraph",{24,1}},"StandardNames"]

Primary

GraphData[{"CayleyGraph",{24,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CayleyGraph",{24,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CayleyGraph",{24,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"CayleyGraph",{24,1}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"CayleyGraph",{24,1}},"EdgeList"]]

Degenerate

GraphData[{"CayleyGraph",{24,1}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CayleyGraph",{24,1}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CayleyGraph",{24,1}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CayleyGraph",{24,1}},"Planar"]

GraphData[{"CayleyGraph",{24,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CayleyGraph",{24,1}},{"RCN","CN"}]

GraphData[{"CayleyGraph",{24,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CayleyGraph",{24,1}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CayleyGraph",{24,1}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"CayleyGraph",{24,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CayleyGraph",{24,1}},"Circulant"]

GraphData[{"CayleyGraph",{24,1}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CayleyGraph",{24,1}},"Halin"]

GraphData[{"CayleyGraph",{24,1}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CayleyGraph",{24,1}},"LCF"]

GraphData[{"CayleyGraph",{24,1}},"HamiltonianCycleCount"]

GraphData[{"CayleyGraph",{24,1}},"LCFSignature"]

GraphData[{"CayleyGraph",{24,1}},"LCFNotations"]

GraphData[{"CayleyGraph",{24,1}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData[{"CayleyGraph",{24,1}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CayleyGraph",{24,1}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CayleyGraph",{24,1}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CayleyGraph",{24,1}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"CayleyGraph",{24,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CayleyGraph",{24,1}}],Debug->True]//Timing

GraphData[{"CayleyGraph",{24,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"CayleyGraph",{24,1}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

gs=LabelGraph/@{RotateGraph[,{22,11}],RotateGraph[,{19,15}],,,}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{24,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{24,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{24,1}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CayleyGraph",{24,1}},"Matchstick"]

GraphData[{"CayleyGraph",{24,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CayleyGraph",{24,1}},"Edges"]]

3D All

GraphData[{"CayleyGraph",{24,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CayleyGraph",{24,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CayleyGraph",{24,1}},"Polyhedral"]

GraphData[{"CayleyGraph",{24,1}},"Graph",{"3D","Polyhedron"}]

{"CayleyGraph", {24, 2}}

Names

GraphData[{"CayleyGraph",{24,2}},"StandardName"]

GraphData[{"CayleyGraph",{24,2}},"StandardNames"]

Primary

GraphData[{"CayleyGraph",{24,2}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CayleyGraph",{24,2}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CayleyGraph",{24,2}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"CayleyGraph",{24,2}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"CayleyGraph",{24,2}},"EdgeList"]]

Degenerate

GraphData[{"CayleyGraph",{24,2}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CayleyGraph",{24,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CayleyGraph",{24,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CayleyGraph",{24,2}},"Planar"]

GraphData[{"CayleyGraph",{24,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CayleyGraph",{24,2}},{"RCN","CN"}]

GraphData[{"CayleyGraph",{24,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CayleyGraph",{24,2}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"CayleyGraph",{24,2}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"CayleyGraph",{24,2}}],"CrossingNumber"->cn]]

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CayleyGraph",{24,2}},"Circulant"]

GraphData[{"CayleyGraph",{24,2}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CayleyGraph",{24,2}},"Halin"]

GraphData[{"CayleyGraph",{24,2}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CayleyGraph",{24,2}},"LCF"]

GraphData[{"CayleyGraph",{24,2}},"HamiltonianCycleCount"]

GraphData[{"CayleyGraph",{24,2}},"LCFSignature"]

GraphData[{"CayleyGraph",{24,2}},"LCFNotations"]

GraphData[{"CayleyGraph",{24,2}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData[{"CayleyGraph",{24,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CayleyGraph",{24,2}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CayleyGraph",{24,2}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CayleyGraph",{24,2}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@%

UnitDistance

GraphData[{"CayleyGraph",{24,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CayleyGraph",{24,2}}],Debug->True]//Timing

GraphData[{"CayleyGraph",{24,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"CayleyGraph",{24,2}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{24,2}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{24,2}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

(ud=FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{24,2}}],MaxIterations->10000])//Timing

UnitDistanceGraphEmbeddingQ[ud]

RotateGraph[Annotate[,VertexLabels->"Name"],{19,20}]

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{24,2}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

UnitDistance exact construction

g=CenterGraph[RotateGraph[Annotate[,VertexLabels->Automatic],{19,1}]]

UnitDistanceGraphEmbeddingQ[g]

{a,b,c}=Norm/@v[[{20,3,15}]]

v=Join[CirclePoints[{a,0},8],CirclePoints[{b,Pi/8},8],CirclePoints[{c,Pi/8},8]];
ee=Select[Subsets[Range[24],{2}],Abs[SquaredEuclideanDistance@@v[[#]]-1]<10^-3&];
g=Graph[Range[24],UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ[g]

DegenerateGraphEmbeddingTypes[g]

v[[{2,9}]][[All,2]]

DegenerateGraphEmbeddingTypes[g]

Clear[a,b,c]

v=Join[CirclePoints[{a,0},8],CirclePoints[{b,Pi/8},8],CirclePoints[{c,Pi/8},8]]

eqn=UnitEdgeEquations[v,ee]//FullSimplify

soln=NSolve[eqn,{a,b,c},Reals]

gs=Graph[Range[24],UndirectedEdge@@@ee,VertexCoordinates->(v/.#)]&/@soln

soln=Solve[eqn,{a,b,c},Reals]

soln=Solve[eqn,{a,b,c},Reals][[{1,2}]]//RootReduce

gs=Graph[Range[24],UndirectedEdge@@@ee,VertexCoordinates->(v/.#)]&/@soln

Matchstick

GraphData[{"CayleyGraph",{24,2}},"Matchstick"]

GraphData[{"CayleyGraph",{24,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CayleyGraph",{24,2}},"Edges"]]

3D All

GraphData[{"CayleyGraph",{24,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CayleyGraph",{24,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CayleyGraph",{24,2}},"Polyhedral"]

GraphData[{"CayleyGraph",{24,2}},"Graph",{"3D","Polyhedron"}]

28

{"CayleyGraph", {28, 1}}

Names

GraphData[{"CayleyGraph",{28,1}},"StandardName"]

GraphData[{"CayleyGraph",{28,1}},"StandardNames"]

Primary

GraphData[{"CayleyGraph",{28,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CayleyGraph",{28,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CayleyGraph",{28,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"CayleyGraph",{28,1}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"CayleyGraph",{28,1}},"EdgeList"]]

Degenerate

GraphData[{"CayleyGraph",{28,1}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CayleyGraph",{28,1}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CayleyGraph",{28,1}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CayleyGraph",{28,1}},"Planar"]

GraphData[{"CayleyGraph",{28,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CayleyGraph",{28,1}},{"RCN","CN"}]

GraphData[{"CayleyGraph",{28,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CayleyGraph",{28,1}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"CayleyGraph",{28,1}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"CayleyGraph",{28,1}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CayleyGraph",{28,1}},"Circulant"]

GraphData[{"CayleyGraph",{28,1}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CayleyGraph",{28,1}},"Halin"]

GraphData[{"CayleyGraph",{28,1}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CayleyGraph",{28,1}},"LCF"]

GraphData[{"CayleyGraph",{28,1}},"HamiltonianCycleCount"]

GraphData[{"CayleyGraph",{28,1}},"LCFSignature"]

GraphData[{"CayleyGraph",{28,1}},"LCFNotations"]

GraphData[{"CayleyGraph",{28,1}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData[{"CayleyGraph",{28,1}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CayleyGraph",{28,1}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CayleyGraph",{28,1}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CayleyGraph",{28,1}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"CayleyGraph",{28,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CayleyGraph",{28,1}}],Debug->True]//Timing

GraphData[{"CayleyGraph",{28,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"CayleyGraph",{28,1}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{28,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{28,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{28,1}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CayleyGraph",{28,1}},"Matchstick"]

GraphData[{"CayleyGraph",{28,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CayleyGraph",{28,1}},"Edges"]]

3D All

GraphData[{"CayleyGraph",{28,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CayleyGraph",{28,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CayleyGraph",{28,1}},"Polyhedral"]

GraphData[{"CayleyGraph",{28,1}},"Graph",{"3D","Polyhedron"}]

30

{"CayleyGraph", {30, 1}}

Names

GraphData[{"CayleyGraph",{30,1}},"StandardName"]

GraphData[{"CayleyGraph",{30,1}},"StandardNames"]

Primary

GraphData[{"CayleyGraph",{30,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CayleyGraph",{30,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CayleyGraph",{30,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"CayleyGraph",{30,1}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"CayleyGraph",{30,1}},"EdgeList"]]

Degenerate

GraphData[{"CayleyGraph",{30,1}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CayleyGraph",{30,1}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CayleyGraph",{30,1}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CayleyGraph",{30,1}},"Planar"]

GraphData[{"CayleyGraph",{30,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CayleyGraph",{30,1}},{"RCN","CN"}]

GraphData[{"CayleyGraph",{30,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CayleyGraph",{30,1}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"CayleyGraph",{30,1}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"CayleyGraph",{30,1}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CayleyGraph",{30,1}},"Circulant"]

GraphData[{"CayleyGraph",{30,1}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CayleyGraph",{30,1}},"Halin"]

GraphData[{"CayleyGraph",{30,1}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CayleyGraph",{30,1}},"LCF"]

GraphData[{"CayleyGraph",{30,1}},"LCFSignature"]

GraphData[{"CayleyGraph",{30,1}},"Graph","LCF"]//StyleGraphs

LCF compute all

Divisors[GraphData[{"CayleyGraph",{30,1}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CayleyGraph",{30,1}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CayleyGraph",{30,1}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CayleyGraph",{30,1}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"CayleyGraph",{30,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CayleyGraph",{30,1}}],Debug->True]//Timing

GraphData[{"CayleyGraph",{30,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"CayleyGraph",{30,1}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,1}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CayleyGraph",{30,1}},"Matchstick"]

GraphData[{"CayleyGraph",{30,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CayleyGraph",{30,1}},"Edges"]]

3D All

GraphData[{"CayleyGraph",{30,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CayleyGraph",{30,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CayleyGraph",{30,1}},"Polyhedral"]

GraphData[{"CayleyGraph",{30,1}},"Graph",{"3D","Polyhedron"}]

{"CayleyGraph", {30, 2}}

GraphData[{"CayleyGraph",{30,2}},"StandardName"]

Primary

GraphData[{"CayleyGraph",{30,2}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CayleyGraph",{30,2}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CayleyGraph",{30,2}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"CayleyGraph",{30,2}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"CayleyGraph",{30,2}},"EdgeList"]]

Degenerate

GraphData[{"CayleyGraph",{30,2}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CayleyGraph",{30,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CayleyGraph",{30,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CayleyGraph",{30,2}},"Planar"]

GraphData[{"CayleyGraph",{30,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CayleyGraph",{30,2}},{"RCN","CN"}]

GraphData[{"CayleyGraph",{30,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CayleyGraph",{30,2}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"CayleyGraph",{30,2}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"CayleyGraph",{30,2}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CayleyGraph",{30,2}},"Circulant"]

GraphData[{"CayleyGraph",{30,2}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CayleyGraph",{30,2}},"Halin"]

GraphData[{"CayleyGraph",{30,2}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CayleyGraph",{30,2}},"LCF"]

GraphData[{"CayleyGraph",{30,2}},"LCFSignature"]

GraphData[{"CayleyGraph",{30,2}},"Graph","LCF"]//StyleGraphs

LCF compute all

Divisors[GraphData[{"CayleyGraph",{30,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CayleyGraph",{30,2}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CayleyGraph",{30,2}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CayleyGraph",{30,2}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"CayleyGraph",{30,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CayleyGraph",{30,2}}],Debug->True]//Timing

GraphData[{"CayleyGraph",{30,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"CayleyGraph",{30,2}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,2}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,2}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,2}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CayleyGraph",{30,2}},"Matchstick"]

GraphData[{"CayleyGraph",{30,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CayleyGraph",{30,2}},"Edges"]]

3D All

GraphData[{"CayleyGraph",{30,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CayleyGraph",{30,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CayleyGraph",{30,2}},"Polyhedral"]

GraphData[{"CayleyGraph",{30,2}},"Graph",{"3D","Polyhedron"}]

{"CayleyGraph", {30, 3}}

Names

GraphData[{"CayleyGraph",{30,3}},"StandardName"]

GraphData[{"CayleyGraph",{30,3}},"StandardNames"]

Primary

GraphData[{"CayleyGraph",{30,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CayleyGraph",{30,3}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CayleyGraph",{30,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CayleyGraph",{30,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CayleyGraph",{30,3}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CayleyGraph",{30,3}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CayleyGraph",{30,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CayleyGraph",{30,3}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CayleyGraph",{30,3}},"Planar"]

GraphData[{"CayleyGraph",{30,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CayleyGraph",{30,3}},{"RCN","CN"}]

GraphData[{"CayleyGraph",{30,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CayleyGraph",{30,3}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"CayleyGraph",{30,3}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"CayleyGraph",{30,3}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CayleyGraph",{30,3}},"Circulant"]

GraphData[{"CayleyGraph",{30,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CayleyGraph",{30,3}},"Halin"]

GraphData[{"CayleyGraph",{30,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CayleyGraph",{30,3}},"LCF"]

GraphData[{"CayleyGraph",{30,3}},"LCFSignature"]

GraphData[{"CayleyGraph",{30,3}},"Graph","LCF"]//StyleGraphs

LCF compute all

Divisors[GraphData[{"CayleyGraph",{30,3}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CayleyGraph",{30,3}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CayleyGraph",{30,3}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CayleyGraph",{30,3}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"CayleyGraph",{30,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CayleyGraph",{30,3}}],Debug->True]//Timing

GraphData[{"CayleyGraph",{30,3}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"CayleyGraph",{30,3}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,3}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,3}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CayleyGraph",{30,3}},"Matchstick"]

GraphData[{"CayleyGraph",{30,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CayleyGraph",{30,3}},"Edges"]]

3D All

GraphData[{"CayleyGraph",{30,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CayleyGraph",{30,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CayleyGraph",{30,3}},"Polyhedral"]

GraphData[{"CayleyGraph",{30,3}},"Graph",{"3D","Polyhedron"}]

{"CayleyGraph", {30, 4}}

GraphData[{"CayleyGraph",{30,4}},"StandardName"]

Primary

GraphData[{"CayleyGraph",{30,4}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CayleyGraph",{30,4}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CayleyGraph",{30,4}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CayleyGraph",{30,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CayleyGraph",{30,4}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CayleyGraph",{30,4}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CayleyGraph",{30,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CayleyGraph",{30,4}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CayleyGraph",{30,4}},"Planar"]

GraphData[{"CayleyGraph",{30,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CayleyGraph",{30,4}},{"RCN","CN"}]

GraphData[{"CayleyGraph",{30,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CayleyGraph",{30,4}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"CayleyGraph",{30,4}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"CayleyGraph",{30,4}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CayleyGraph",{30,4}},"Circulant"]

GraphData[{"CayleyGraph",{30,4}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CayleyGraph",{30,4}},"Halin"]

GraphData[{"CayleyGraph",{30,4}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CayleyGraph",{30,4}},"LCF"]

GraphData[{"CayleyGraph",{30,4}},"LCFSignature"]

GraphData[{"CayleyGraph",{30,4}},"Graph","LCF"]//StyleGraphs

LCF compute all

Divisors[GraphData[{"CayleyGraph",{30,4}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CayleyGraph",{30,4}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CayleyGraph",{30,4}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CayleyGraph",{30,4}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"CayleyGraph",{30,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CayleyGraph",{30,4}}],Debug->True]//Timing

GraphData[{"CayleyGraph",{30,4}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"CayleyGraph",{30,4}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,4}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"CayleyGraph",{30,4}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CayleyGraph",{30,4}},"Matchstick"]

GraphData[{"CayleyGraph",{30,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CayleyGraph",{30,4}},"Edges"]]

3D All

GraphData[{"CayleyGraph",{30,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CayleyGraph",{30,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CayleyGraph",{30,4}},"Polyhedral"]

GraphData[{"CayleyGraph",{30,4}},"Graph",{"3D","Polyhedron"}]

Illustrations

Cayley Graph of (Subscript[D, 7])

DihedralGroup[7]

Connected graph generated by a rotation and a flip

Now take any two generators for (Subscript[D, 7]), one corresponding to rotations (shifting of the permutation), and one to flips (reversing the order of the permutation).

DihedralGroup[7][[{2,8}]]

ShowGraph[d7=CayleyGraph[DihedralGroup[7],{2,8}]]

ConnectedQ[d7]

So 2 and 8 generate (Subscript[D, 7])

But this is isomorphic to the prism graph (Subscript[Y, 7])

IsomorphicQ[PrismGraph[7],MakeUndirected[d7]]

ShowGraph[niced7=SetGraphOptions[ChangeVertices[MakeGraph[Range[14],
(#1<8&&#2<8&&Mod[#2-#1,7]==1)||
(#1>7&&#2>7&&Mod[#1-#2,7]==1)||
(Abs[#2-#1]==7)&
],Vertices[PrismGraph[7]]],Join[Flatten[{#,Reverse[#]}&/@Table[{i,i+7},{i,7}],1],{EdgeColor->Red}],EdgeColor->Blue],
VertexStyle->Disk[.04]]

IsomorphicQ[niced7,d7]

Disconnected graph generated by two rotations

DihedralGroup[7][[{2,3}]]

ShowGraph[d72=CayleyGraph[DihedralGroup[7],{2,3}]]

ShowGraph[niced72=SetGraphOptions[ChangeVertices[MakeGraph[Range[14],
(#1<8&&#2<8&&1<=Mod[#2-#1,7]≤2)||
(#1>7&&#2>7&&1<=Mod[#1-#2,7]≤2)&
],Vertices[PrismGraph[7]]],Join[Flatten[{#,Reverse[#]}&/@Table[{i,i+7},{i,7}],1],{EdgeColor->Red}],EdgeColor->Blue],
VertexStyle->Disk[.04]]

IsomorphicQ[niced72,d72]

ShowGraphArray[{niced7,niced72},VertexStyle->Disk[.04]]

Other Graphs

ShowGraphArray[{d7,d72=CayleyGraph[DihedralGroup[7],{2,3}]}]

ConnectedQ[d72]

So elements 2 and 3 do not generate (Subscript[D, 7]).  In general, here are the pairs of elements that *do* generate (Subscript[D, 7]).

Timing[generators=Select[KSubsets[Range[2,14],2],ConnectedQ[CayleyGraph[DihedralGroup[7],#]]&]]

And here are the pairs of elements that *do not* generate (Subscript[D, 7]).

nongenerators=Complement[KSubsets[Range[2,14],2],generators]

Length[nongenerators]

Binomial[6,2]

ColumnForm[DihedralGroup[7][[#]]&/@nongenerators]

Disconnected graph generated by three rotations

DihedralGroup[7][[{2,3,4}]]

ShowGraph[CayleyGraph[DihedralGroup[7],Range[2,4]]]

Complete graph generated by all nonidentity elements

ShowGraph[CayleyGraph[DihedralGroup[7],Range[2,14]]]

Partial Cayley Graph of (Subscript[A, 4])

The Cayley graph depends on the choice of a generating set.  Here is the Cayley graph for the alternating group (Subscript[A, 4]).

AlternatingGroup[4]

ShowGraph[a4=CayleyGraph[AlternatingGroup[4],{4,5}],
VertexStyle->Disk[.04],
VertexColor->Red]

ShowGraph[SpringEmbedding[a4],VertexStyle->Disk[.04],
VertexColor->Red]

ShowGraph[nicea4=AddEdges[ChangeVertices[MakeDirected[EmptyGraph[12]],Join[Table[Through[{Cos,Sin}[2Pi i/4]],{i,0,3}]/2,Table[Through[{Cos,Sin}[2Pi(i+1/2)/8]],{i,0,7}]]//N
],Flatten[Partition[#,2,1,1]&/@{{1,5,12},{2,6,7},{3,9,8},{4,10,11},{5,6},{7,8},{9,10},{11,12},{1,3},{2,4}},1]],
VertexColor->Red,
VertexStyle->Disk[.04]
]

r=RecognizeGraph[MakeUndirected[nicea4]]

Full Cayley Graph of (Subscript[A, 4])

CayleyGraph[System`AlternatingGroup[4]]

RecognizeGraph[UndirectedGraph[%]]

Cayley Graph of the Free Group on 2 Generators

The two generators represent horizontal and vertical displacement, respectively.  Each new edge is drawn at half the size to give a fractal picture.

(*The Cayley Graph on the free group of two generators,drawn out to level n.*)
sc=.5;
nof[n_]:=(1-sc^(n+1))/(1-sc)
(*to cut down on the number of lines that need to be drawn*)
qu[0,{x_,y_},{a_,b_}]:={}
qu[n_,{x_,y_},{a_,b_}]:=Module[{a0,b0},{a0,b0}=nof[n-1]{a,b};
Join[{Line[{{x-b0,y-a0},{x+b0,y+a0}}]},qu[n-1,{x-b,y-a},sc{-b,-a}],qu[n-1,{x+b,y+a},sc{b,a}],qu[n-1,{x+a,y+b},sc{a,b}]]]
totqu[n_]:=Module[{l},l=nof[n];
Join[{Line[{{-l,0},{l,0}}],qu[n-1,{1,0},{sc,0}],qu[n-1,{-1,0},{-sc,0}],Line[{{0,-l},{0,l}}],qu[n-1,{0,1},{0,sc}],qu[n-1,{0,-1},{0,-sc}]}]]
shwqu[n_]:=Graphics[totqu[n],AspectRatio->Automatic]

(*note that Table[shwqu[n],{n,8}] makes a neat animation*)
(*The best value for n depends on the resolution desired and memeory*)
(*to save memory the segments are not drawn individually*)
(*also,looking at shwqu[8] makes me think `T is for tree.'*)
{shwqu[3],shwqu[7]}

Show[GraphicsArray[Partition[Table[shwqu[n],{n,6}],3]]]

Export[gifs<>"cayley.gif",Table[shwqu[n],{n,8}]]

Table[Show[shwqu[n]],{n,8}]

Cayley Tetrahedron is F24

By Ed Pegg Jr.

If three vertices of a (Subscript[K, 4]) graph are covered with differently colored stones, and any stone may be moved to the empty vertex, then the graph of all positions forms a Cayley graph.  Connecting lines indicate neighboring positions.

Setup

Graphic

Show[GraphicsArray[
{
Show[CayleyTetrahedron,
AspectRatio->Automatic,
DisplayFunction->Identity
],
ShowGraph[SymmetricCubicGraph2[24],
VertexStyle->Disk[.04],
DisplayFunction->Identity]
}
],
AspectRatio->Automatic]

SymmetricGroup[4]

SymmetricGroup[4][[{7,15,22}]]

ShowGraph[g=CayleyGraph[SymmetricGroup[4],{7,15,22}]]

CubicQ[MakeUndirected[g]]

MyIsomorphicQ[MakeUndirected[g],SymmetricCubicGraph[24]]//Timing

High-Girth

from Royle

gs=ImportString["Ws_G_gIO`Gg_G_C?@?I@?GO?@A_@I??E_?Cg?ACG?_Q???r
Ws`@GOPOGg@OGOO@C@?_CAC??@wH??E???GH?@Cg?EC?ACH
Ys`AA?_G@?A?C?C?@??O?A??Cc_GSOGa_AaO?aW?CgO?KH??Sg??RC??
Zs`@A?_AGaAQBAO_C_?`?AO??@_@?WA?gE????K??AO?@?E?C?I??_c_?_H_
[s`AA?_C?OC?G?C?@??_?A??A_oHAOAS_@SG?bO?Gd??OP?@@C??OW??F??????N
]s`@?_GA?_gCGOA_A_A??G??AGOG_OCGCCAC??W??OO?AA???I???S?_CO?oAG?Q?G?M?@?@S?
]s_a?_GO?_G?A?A?A?@??G??CM?D@_EAODo??EA??Q_??k??Cg??HA??GQ??K??????As???So
]s`@?_GA?_A?A?O?G?@??G??Ag_Ea?HGODAO?@o??h??@P??EC??OI??CI??K??????BK???RO
]s`AA?_C?OC?G?C?@??_?A??C`_AS_CgO@_G?gC?GW??aO??aO??SG???e???EO????ES???e_",{"Graph6"}]

RecognizeGraph/@gs

VertexCount/@gs

Table[a[n]=0,{n,40}]

Print[GraphDataString[#,
"StandardName"->{"CayleyGraph",{n=V[#],++a[n]}},
"Name"->"("<>ToString[n]<>","<>ToString[a[n]]<>")-Cayley graph",
"Classes"->{"CayleyGraph"},
"Information"->{"CayleyGraph"},
Debug->True,
TimeConstraint->600
]]&/@Delete[gs,{{3},{4}}];

Counts

cay={1,2,2,4,3,8,4,14,9,20,8,74,14,56,44,278,36,376,60,1132,240,816,188,15394,464,4104,1434,25784,1182,45184,2192};

Grid[
Table[{n,cay[[n]],GraphData["Cayley",n]//Length},
{n,Length[cay]}],
Dividers->All,Alignment->Decimal
]//TraditionalForm

Checks

SetDirectory[$dir="/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/Royle/Noncayley/"];

Missing

Select[GraphData[;;31],MissingQ[GraphData[#1,"Cayley"]]&]

Test

DeleteCases[
Monitor[{gn=#,GraphData[#,"Cayley"],CayleyGraphQ[GraphData[#]]}&/@GraphData[;;31],gn],
{_,x_,x_}]//Timing

n for which All VT graphs are Cayley

allc=Join[Range[9],Range[11,14],{17,19,21,22,23,25,27,29,31}]

Function[g,Select[GraphData["VertexTransitive",g],GraphData[#,"Cayley"]=!=True&]]/@allc

Orders for which non-Cayley VT graphs exist

nonc=Complement[Range[31],allc]

Disconnected Non-Cayley graphs of various orders

Grid[{#,Select[Import[$dir<>"noncay"<>ToString[#]<>".g6"],!ConnectedGraphQ[#]&]}&/@Take[nonc,All],Dividers->All,Alignment->Left]

Grid[{#,RecognizeGraph/@Select[Import[$dir<>"noncay"<>ToString[#]<>".g6"],!ConnectedGraphQ[#]&]}&/@Take[nonc,All],Dividers->All,Alignment->Left]

Grid[{#,Map[RecognizeGraph,ConnectedGraphComponents/@Select[Import[$dir<>"noncay"<>ToString[#]<>".g6"],!ConnectedGraphQ[#]&],{2}]}&/@Take[nonc,All],Dividers->All,Alignment->Left]

Disconnected non-Cayley VT graphs

10

RecognizeGraph/@Import[$dir<>"noncay10.g6"]

Select[GraphData["VertexTransitive",10],GraphData[#,"Noncayley"]&]

15

Sort[Select[GraphData["VertexTransitive",15],GraphData[#,"Noncayley"]&]]

Sort[RecognizeGraph/@Import[$dir<>"noncay15.g6"]]

16

Select[GraphData["VertexTransitive",16],GraphData[#,"Noncayley"]&]

DeleteCases[Sort[RecognizeGraph/@Import[$dir<>"noncay16.g6"]],{}]

18

Select[GraphData["VertexTransitive",18],GraphData[#,"Noncayley"]&]

Sort[RecognizeGraph/@Import[$dir<>"noncay18.g6"]]

20

l1=Sort@Select[GraphData["VertexTransitive",20],GraphData[#,"Noncayley"]&]

l2=DeleteCases[Sort[RecognizeGraph/@Import[$dir<>"noncay20.g6"]],{}]

Equal@@Sort/@{l1,l2}

24

l1=Sort@Select[GraphData["VertexTransitive",24],GraphData[#,"Noncayley"]&]

l2=DeleteCases[Sort[RecognizeGraph/@Import[$dir<>"noncay24.g6"]],{}]

Equal@@Sort/@{l1,l2}

26

l1=Select[GraphData["VertexTransitive",26],GraphData[#,"Noncayley"]&]

l2=DeleteCases[Sort[RecognizeGraph/@Import[$dir<>"noncay26.g6"]],{}]

Equal@@Sort/@{l1,l2}

28

l1=Select[GraphData["VertexTransitive",28],GraphData[#,"Noncayley"]&]

l2=DeleteCases[Sort[RecognizeGraph/@Import[$dir<>"noncay28.g6"]],{}]

Equal@@Sort/@{l1,l2}

30

l1=Select[GraphData["VertexTransitive",30],GraphData[#,"Noncayley"]&]

l2=SortBy[DeleteCases[RecognizeGraph/@Import[$dir<>"noncay30.g6"],{}],First[Flatten[{#}]]&]

Equal@@Sort/@{l1,l2}

Enumeration by AbelianGroup

(c2=DeleteCases[{#,RecognizeGraph[UndirectedGraph[CayleyGraph[AbelianGroup[#]]]]}&/@Flatten[Table[{j,i},{i,2,20},{j,2,i}],1],{_,{}}])//Timing

Grid[{#[[1]],#[[2]],GetGraphData[#[[2]],"File"],Cases[GraphData[#[[2]],"CayleyGraphGeneratingGroupNames"],{"Abelian",_}]}&/@c2,Dividers->All,Alignment->{{Left,Left,Decimal,Left},Automatic}]//TraditionalForm

(c3=DeleteCases[Monitor[{g=#,RecognizeGraph[UndirectedGraph[CayleyGraph[AbelianGroup[#]]]]}&/@Flatten[Table[{k,j,i},{i,2,15},{j,2,i},{k,2,j}],2],g],{_,{}}])//Timing

Grid[{#[[1]],#[[2]],GetGraphData[#[[2]],"File"],Cases[GraphData[#[[2]],"CayleyGraphGeneratingGroupNames"],{"Abelian",_}]}&/@c3,Dividers->All,Alignment->{{Left,Left,Decimal,Left},Automatic}]//TraditionalForm

(c4=DeleteCases[Monitor[{g=#,RecognizeGraph[UndirectedGraph[CayleyGraph[AbelianGroup[#]]]]}&/@Flatten[Table[{l,k,j,i},{i,2,10},{j,2,i},{k,2,j},{l,2,k}],3],g],{_,{}}])//Timing

Grid[{#[[1]],#[[2]],GetGraphData[#[[2]],"File"],Cases[GraphData[#[[2]],"CayleyGraphGeneratingGroupNames"],{"Abelian",_}]}&/@c4,Dividers->All,Alignment->{{Left,Left,Decimal,Left},Automatic}]//TraditionalForm

(c5=DeleteCases[Monitor[{g=#,RecognizeGraph[UndirectedGraph[CayleyGraph[AbelianGroup[#]]]]}&/@Flatten[Table[{m,l,k,j,i},{i,2,6},{j,2,i},{k,2,j},{l,2,k},{m,2,l}],4],g],{_,{}}])//Timing

Grid[{#[[1]],#[[2]],GetGraphData[#[[2]],"File"],Cases[GraphData[#[[2]],"CayleyGraphGeneratingGroupNames"],{"Abelian",_}]}&/@c5,Dividers->All,Alignment->{{Left,Left,Decimal,Left},Automatic}]//TraditionalForm

(c6=DeleteCases[Monitor[{g=#,RecognizeGraph[UndirectedGraph[CayleyGraph[AbelianGroup[#]]]]}&/@Flatten[Table[{n,m,l,k,j,i},{i,2,5},{j,2,i},{k,2,j},{l,2,k},{m,2,l},{n,2,m}],5],g],{_,{}}])//Timing

Grid[{#[[1]],#[[2]],GetGraphData[#[[2]],"File"],Cases[GraphData[#[[2]],"CayleyGraphGeneratingGroupNames"],{"Abelian",_}]}&/@c6,Dividers->All,Alignment->{{Left,Left,Decimal,Left},Automatic}]//TraditionalForm

Enumeration by permutation generators

FindCayleyGraphs[n_,k_:All,t_:All]:=DeleteCases[{RecognizeGraph[MyCayleyGraph[#]],#}&/@Take[If[k===All,Rest,Identity][Developer`ToPackedArray[Subsets[Permutations[Range[n]],k]]],t],{{},_}]
CayleyGraphList[l_]:={#[[1,1]],Last/@#}&/@Split[Sort[l],First[#1]==First[#2]&]
NewCayleyGraphs[c_]:=Select[c,Head[GraphData[#[[1]],"CayleyGraphGeneratingGroups"]]===Missing&]

cayleys=Select[GraphData[All],ListQ["CayleyGraph"/.GraphData[#,"NotationRules"]]&];

Table

Grid[Sort[{GraphData[#,"Name"],"CayleyGraph"/.GraphData[#,"NotationRules"]}&/@GraphData["CayleyGraph"]],Dividers->All,Alignment->Left]//TraditionalForm

2

(c=FindCayleyGraphs[2,All])//Timing

(n=CayleyGraphList[c])//ColumnForm

NewCayleyGraphs[n]

(3,1)

(c=FindCayleyGraphs[3,{1}]);//Timing

(n=CayleyGraphList[c])//Column

NewCayleyGraphs[n]

3

(c=FindCayleyGraphs[3,All]);//Timing

(n=CayleyGraphList[c])//ColumnForm

NewCayleyGraphs[n]

(4,2)

(c=FindCayleyGraphs[4,{2}]);//Timing

(n=CayleyGraphList[c])//Column

NewCayleyGraphs[n]

(4,3)

(c=FindCayleyGraphs[4,{3}]);//Timing

(n=CayleyGraphList[c])

NewCayleyGraphs[n]

(4,4)

(c=FindCayleyGraphs[4,{4}]);//Timing

(n=CayleyGraphList[c])

NewCayleyGraphs[n]

(5,1)

(c=FindCayleyGraphs[5,{1}]);//Timing

(n=CayleyGraphList[c])//ColumnForm

NewCayleyGraphs[n]

(5,2)

(c=FindCayleyGraphs[5,{2}]);//Timing

(n=CayleyGraphList[c]);

NewCayleyGraphs[n]

(5,3)

All at once

(c=FindCayleyGraphs[5,{3}]);//Timing

(n=CayleyGraphList[c]);

NewCayleyGraphs[n]

Piecewise

ByteCount[s=Developer`ToPackedArray[Subsets[Permutations[5],{3}]]]/10^6.

Monitor[Do[If[(rg=RecognizeGraph[CayleyGraph[p=s[[i]]]])=!={}&&!MemberQ[cayleys,rg],AppendTo[cayleys,rg];Print[{rg,{p}}]],{i,Length[s]}],{i,"/",Length[s]}]

(5,4)

ByteCount[s=Developer`ToPackedArray[Subsets[Permutations[5],{4}]]]/10^6.

cayleys=GraphData["CayleyGraph"];

Monitor[Do[If[(rg=RecognizeGraph[CayleyGraph[p=s[[i]]]])=!={}&&!MemberQ[cayleys,rg],AppendTo[cayleys,rg];Print[{rg,{p}}]],{i,6603000,Length[s]}],{i,"/",Length[s]}]

5 misc.

{#[[1,1]],Last/@#}&/@Split[Sort[l],First[#1]==First[#2]&]//ColumnForm

(6,1)

(c=FindCayleyGraphs[6,{1}]);//Timing

(n=CayleyGraphList[c])//ColumnForm

NewCayleyGraphs[n]

(6,2)

All at once

(c=FindCayleyGraphs[6,{2}]);//Timing

...takes a long time...

(n=CayleyGraphList[c])//ColumnForm

NewCayleyGraphs[n]

Piecewise

ByteCount[s=Developer`ToPackedArray[Subsets[Permutations[6],{2}]]]/10^6.

Monitor[Do[If[(rg=RecognizeGraph[CayleyGraph[p=s[[i]]]])=!={}&&!MemberQ[cayleys,rg],AppendTo[cayleys,rg];Print[{rg,{p}}]],{i,Length[s]}],{i,"/",Length[s]}]

1000

(l=DeleteCases[{recognizeGraph@@#,#}&/@Take[Subsets[Permutations[Range[6]],{2}],1000],{{},_}]);//Timing

{#[[1,1]],Last/@#}&/@Split[Sort[l],First[#1]==First[#2]&]//ColumnForm

10000

(l=DeleteCases[{recognizeGraph@@#,#}&/@Take[Subsets[Permutations[Range[6]],{2}],10^4],{{},_}]);//Timing

{#[[1,1]],Last/@#}&/@Split[Sort[l],First[#1]==First[#2]&]//ColumnForm

(6,3)

ByteCount[s=Developer`ToPackedArray[Subsets[Permutations[6],{3}]]]/10^6.

Monitor[Do[If[(rg=RecognizeGraph[CayleyGraph[p=s[[i]]]])=!={}&&!MemberQ[cayleys,rg],AppendTo[cayleys,rg];Print[{rg,{p}}]],{i,140504,Length[s]}],{i,"/",Length[s]}]

(7,1)

ByteCount[s=Developer`ToPackedArray[Subsets[Permutations[7],{1}]]]/10^6.

Monitor[Do[If[(rg=RecognizeGraph[CayleyGraph[p=s[[i]]]])=!={}&&!MemberQ[cayleys,rg],AppendTo[cayleys,rg];Print[{rg,{p}}]],{i,1,Length[s]}],{i,"/",Length[s]}]

(7,2)

ByteCount[s=Developer`ToPackedArray[Subsets[Permutations[7],{2}]]]/10^6.

Monitor[Do[If[(rg=RecognizeGraph[CayleyGraph[p=s[[i]]]])=!={}&&!MemberQ[cayleys,rg],AppendTo[cayleys,rg];Print[{rg,{p}}]],{i,1,Length[s]}],{i,"/",Length[s]}]

Enumeration by FiniteGroupData

PermutationGroupRepresentation

But there is disagreement between "CayleyGraph" and CayleyGraph[PermutationGroup[...]] for 22 groups in V12.1.1

Length[groups=DeleteCases[{#,FiniteGroupData[#,"PermutationGroupRepresentation"],FiniteGroupData[#,"Order"]}&/@FiniteGroupData[All],{_,_Missing,_}]]

graphsizes=Union[GraphData[#,"V"]&/@GraphData[All]];

Length[groups2=Select[groups,MemberQ[graphsizes,#[[-1]]]&][[All,;;2]]]

data=Monitor[{g=#1,#2,TimeConstrained[RecognizeGraph[UndirectedGraph[CayleyGraph[#2]]],60]}&@@@Take[groups2,All],g];//Timing

Cases[data2,{gname_,grp_,$Aborted}:>{FiniteGroupData[gname,"Order"],gname,grp}]

TextGrid[Cases[data,{_,_,{}}][[All,;;2]],Dividers->All]

TextGrid[cgdata={#[[1,-1]],Union[#[[All,1]]],Union[#[[All,2]]]}&/@SplitBy[SortBy[DeleteCases[data,{_,_,{}}],Last],Last],Dividers->All]